Sketching Approximability of Symmetric Boolean CSPs
Author
Noah Singer
Title
Sketching Approximability of Symmetric Boolean CSPs
Description
Code for paper by Boyland, Hwang, Prasad, Singer, Velusamy: https://arxiv.org/abs/2112.06319v1]
Category
Academic Articles & Supplements
Keywords
URL
http://www.notebookarchive.org/2022-03-a5vpzhg/
DOI
https://notebookarchive.org/2022-03-a5vpzhg
Date Added
2022-03-22
Date Last Modified
2022-03-22
File Size
86.03 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
This file contains supplementary data for Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer and Santhoshini Velusamy, “Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs.” https://arxiv.org/abs/2112.06319v1.
Sketching Approximability of Symmetric Boolean CSPs
Sketching Approximability of Symmetric Boolean CSPs
Noah Singer
<noahsinger@college.harvard.edu>
updated 12-11-2021
updated 12-11-2021
Code
Code
In[]:=
$MaxExtraPrecision=1000
In[]:=
(* Coefficient of p_i in mu_k *)
In[]:=
epsilon[i_,k_]:=-1+2*i/k
In[]:=
(*Unfortunately,Mathematica1-indexesarrays;Iwilluseour'spapernotation,sop_i=D[[i+1]]*)
In[]:=
mu[k_,D_]:=Sum[epsilon[i,k]*D[[i+1]],{i,0,k}]
In[]:=
gammaA[S_,k_,D_]:=(1+mu[k,D])/(1+epsilon[Min[S],k])
In[]:=
gammaB[S_,k_,D_]:=1
In[]:=
gammaC[S_,k_,D_]:=(1-mu[k,D])/(1-epsilon[Max[S],k])
In[]:=
gamma[S_,k_,D_]:=Piecewise[{{gammaA[S,k,D],-1<=mu[k,D]<epsilon[Min[S],k]},{gammaB[S,k,D],epsilon[Min[S],k]<=mu[k,D]≤epsilon[Max[S],k]},{gammaC[S,k,D],epsilon[Max[S],k]<mu[k,D]≤1}}]
In[]:=
(*Takescareofnegativepowers*)
In[]:=
power[base_,exp_]:=If[exp<=0,1,base^exp]
In[]:=
lambdaCoeff[S_,k_,p_,i_]:=Sum[Sum[Binomial[i,j]*Binomial[k-i,s-j]*power[1-p,s+i-2*j]*power[p,k-s-i+2*j],{j,Max[0,s-k+i],Min[i,s]}],{s,S}]
In[]:=
lambda[S_,k_,D_,p_]:=Sum[lambdaCoeff[S,k,p,i]*D[[i+1]],{i,0,k}]
In[]:=
(*Computationsforbetaandalpha,withsymbolic(S)variants;sorryforviolatingDRY,buttheoptimizerneedsitlikethis!*)
In[]:=
beta[S_,k_,D_]:=NMaxValue[{lambda[S,k,D,p],0≤p≤1},p]/;ArrayQ[D,1,NumberQ];
In[]:=
betaS[S_,k_,D_]:=MaxValue[{lambda[S,k,D,p],0≤p≤1},p]
In[]:=
betaPair[S_,k_,D_]:=NMaximize[{lambda[S,k,D,p],0≤p≤1},p]/;ArrayQ[D,1,NumberQ];
In[]:=
betaPairS[S_,k_,D_]:=Maximize[{lambda[S,k,D,p],0≤p≤1},p]
In[]:=
alpha[S_,k_,D_]:=beta[S,k,D]/gamma[S,k,D]/;ArrayQ[D,1,NumberQ];
In[]:=
alphaS[S_,k_,D_]:=betaS[S,k,D]/gamma[S,k,D]
In[]:=
rho[S_,k_]:=Sum[Binomial[k,i],{i,S}]/2^k
In[]:=
(*CheckwhethersomeD_Nparticipatesinapadded1-wisepair*)
In[]:=
testP1WP[S_,k_,DN_]:=Module[{system},With[{DY=Array[DistY,k+1],D0=Array[Dist0,k+1]},(system=Sum[DY[[i+1]],{i,S}]gamma[S,k,DN]&&DY-tau*D0≥0&&DN-tau*D0≥0&&mu[k,(DY-tau*D0)/(1-tau)]0&&mu[k,(DN-tau*D0)/(1-tau)]0&&D0≥0&&Total[D0]1&&DY≥0&&Total[DY]1&&0≤tau≤1;FindInstance[system,Join[{tau},D0,DY]])]]
In[]:=
(*Testwhether"min-max method"sufficestolowerboundalphaataparticularD_N*)
In[]:=
Options[testMinMax]={"TestP1WP"False};
In[]:=
Options[maxMinLBs]={"Piecewise"True}
In[]:=
maxMinLBs[S_,k_,p_,OptionsPattern[]]:=Module[{Dist,programs},With[{D=Array[Dist,k+1]},(programs={{lambda[S,k,D,p]/gammaA[S,k,D],If[OptionValue["Piecewise"],mu[k,D]<epsilon[Min[S],k],Nothing]},{lambda[S,k,D,p],If[OptionValue["Piecewise"],epsilon[Min[S],k]≤mu[k,D]≤epsilon[Max[S],k],Nothing]},If[Max[S]<k,{lambda[S,k,D,p]/gammaC[S,k,D],If[OptionValue["Piecewise"],epsilon[Max[S],k]<mu[k,D],Nothing]},Nothing](*lastcaseonlymakessensewhenMax[S]<k,elsegammaisundefined*)};(MinValue[Join[#,{Total[D]1,D≥0}],D]//Simplify)&/@programs)]]
In[]:=
testMinMax[S_,k_,D_,OptionsPattern[]]:=Module[{pForD,alphaForD,alphaLB,nonPiecewiseLBs},(Print[StringForm["Calculated gamma for D: ``",gamma[S,k,D]]];pForD=p/.Last[betaPairS[S,k,D]]//Simplify;Print[StringForm["Calculated p for D: ``",pForD]];alphaForD=alphaS[S,k,D]//Simplify;Print[StringForm["Calculated alpha for D: ``",ToRadicals[alphaForD]]];alphaLB=Min[maxMinLBs[S,k,pForD]];nonPiecewiseLBs=maxMinLBs[S,k,pForD,"Piecewise"False];Print[StringForm["Lower bound on alpha using min-max: ``",ToRadicals[alphaLB]]];Print[StringForm["Numerical comparison: trivialLB(alpha) = ``, LB(alpha) = ``, UB(alpha) = ``, trivialUB(alpha) = ``",N[rho[S,k]],N[alphaLB,30],N[alphaForD,30],N[2*rho[S,k]]]];Print[StringForm["Ratio: ``",N[alphaForD/alphaLB]]];Print[StringForm["Lower bounds without piecewise: `` (``)",nonPiecewiseLBs,N[nonPiecewiseLBs]]];If[OptionValue["TestP1WP"],Print[StringForm["Padded 1-wise pair? ``",testP1WP[S,k,D]]],Nothing];)]
In[]:=
(*Numericallyestimatethebestapproximationratio;seeexamplesbelow*)
In[]:=
Options[estimateAlpha]={"Support"All,"Symbolic"False,"TestMinMax"True,"MonitorSteps"False}
In[]:=
expand[support_,k_,Dsparse_]:=Normal[SparseArray[support+1Dsparse,k+1]]
In[]:=
estimateAlpha[S_,k_,OptionsPattern[]]:=Module[{minimizerToApply,alphaToApply,minimizerOptions,support,alphaUB,DSAsgn,DUB,Dist},(minimizerToApply=If[OptionValue["Symbolic"],Minimize,NMinimize];alphaToApply=If[OptionValue["Symbolic"],alphaS,alpha];support=If[OptionValue["Support"]===All,Range[0,k],OptionValue["Support"]];Print[StringForm["Estimating alpha for S = ``, k = ``, on distributions with support ``",S,k,support]];With[{Dsparse=Array[Dist,Length[support]]},(minimizerOptions=If[OptionValue["MonitorSteps"],{"EvaluationMonitor"Print[StringForm["Examined @ ``, alpha = ``",expand[support,k,Dsparse],alpha[S,k,expand[support,k,Dsparse]]]]},{}];{alphaUB,DSAsgn}=minimizerToApply[{alphaToApply[S,k,expand[support,k,Dsparse]],Total[Dsparse]1,Dsparse≥0},Dsparse,Evaluate@minimizerOptions])];DUB=expand[support,k,Dist[#]/.DSAsgn&/@Range[Length[support]]];Print[StringForm["Upper bound on alpha: `` (``)",alphaUB,N[alphaUB,30]]];Print[StringForm["Corresponding D: `` (``)",DUB,N[DUB,30]]];If[OptionValue["TestMinMax"],testMinMax[S,k,DUB],Nothing];)]
Examples of minmax method
Examples of minmax method
kAND
kAND
In[]:=
testMinMax[{3},3,{0,0,1,0}]
In[]:=
testMinMax[{6},6,{0,0,0,16/25,9/25,0,0}]
Other cases we managed to solve
Other cases we managed to solve
In[]:=
testMinMax[{2,3},3,{0,1/2,0,1/2}]
In[]:=
P2[z_]:=-908+5021z-9001z^2+5158z^3
In[]:=
rootP2=Root[P2[z],1]
In[]:=
testMinMax[{4,5},5,{0,0,1-rootP2,rootP2,0,0}]
In[]:=
P5[z_]:=-344+1770z-3102z^2+1811z^3
In[]:=
rootP5=Root[P5[z],1]
In[]:=
testMinMax[{4},5,{0,0,1-rootP5,rootP5,0,0}]
In[]:=
testMinMax[{3,4},4,{0,0,4/5,1/5,0},"TestP1WP"True]
In[]:=
testMinMax[{3,4,5},5,{0,1/2,0,0,0,1/2}]
S = {k - 1, k} where k even
S = {k - 1, k} where k even
In[]:=
testMinMax[{5,6},6,{0,0,0,9/13,4/13,0,0}]
In[]:=
testMinMax[{7,8},8,{0,0,0,0,16/25,9/25,0,0,0}]
In[]:=
testMinMax[{9,10},10,{0,0,0,0,0,25/41,16/41,0,0,0,0}]
In[]:=
testMinMax[{11,12},12,{0,0,0,0,0,0,36/61,25/61,0,0,0,0,0}]
In[]:=
12/2*(((12-2)*12)/(4(12-1)^2))^((12-2)/2)//Simplify
S = {(k + 1)/2} where k odd, and related examples (where S is close to (k + 1)/2 )
S = {(k + 1)/2} where k odd, and related examples (where S is close to (k + 1)/2 )
In[]:=
testMinMax[{2},3,{1/3,0,0,2/3}]
In[]:=
testMinMax[{3},5,{2/5,0,0,0,0,3/5}]
In[]:=
testMinMax[{3,4},5,{2/5,0,0,0,0,3/5}]
In[]:=
testMinMax[{4},7,{3/7,0,0,0,0,0,0,4/7}]
In[]:=
testMinMax[{4,5},7,{3/7,0,0,0,0,0,0,4/7}]
In[]:=
testMinMax[{5},9,{4/9,0,0,0,0,0,0,0,0,5/9}]
In[]:=
testMinMax[{5,6},9,{4/9,0,0,0,0,0,0,0,0,5/9}]
In[]:=
testMinMax[{5,6,7},9,{4/9,0,0,0,0,0,0,0,0,5/9}]
In[]:=
testMinMax[{5,7},9,{4/9,0,0,0,0,0,0,0,0,5/9}]
In[]:=
testMinMax[{6},11,{5/11,0,0,0,0,0,0,0,0,0,0,6/11}]
In[]:=
testMinMax[{6,7},11,{5/11,0,0,0,0,0,0,0,0,0,0,6/11}]
In[]:=
testMinMax[{6,7,8},11,{5/11,0,0,0,0,0,0,0,0,0,0,6/11}]
In[]:=
testMinMax[{6,8},11,{5/11,0,0,0,0,0,0,0,0,0,0,6/11}]
In[]:=
testMinMax[{7},13,{6/13,0,0,0,0,0,0,0,0,0,0,0,0,7/13}]
In[]:=
testMinMax[{7,8},13,{6/13,0,0,0,0,0,0,0,0,0,0,0,0,7/13}]
In[]:=
testMinMax[{7,8,9},13,{6/13,0,0,0,0,0,0,0,0,0,0,0,0,7/13}]
In[]:=
testMinMax[{7,8,9,10},13,{6/13,0,0,0,0,0,0,0,0,0,0,0,0,7/13}]
In[]:=
testMinMax[{8},15,{7/15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8/15}]
Examples where we don' t get exact solution
Examples where we don' t get exact solution
In[]:=
testMinMax[{4,5,6,7},7,{0,1/2,0,0,0,0,0,1/2}]
testMinMax[{3},4,{0,1/2,0,1/2,0}]testMinMax[{3,5},5,{1/4,0,0,0,3/4,0}]
In[]:=
testMinMax[{6,7,8},8,{0,0,0,0,9/13,4/13,0,0,0}]
In[]:=
testMinMax[{4,5,6},6,{0,0,0,0.930013,0,0,0.069987}]
“Support 2 minmax method” fails in certain cases
“Support 2 minmax method” fails in certain cases
(*Thisfunctionchecksminmaxoverallpossibledistributionswithsupportsize2*)
In[]:=
Options[testDistsWithSupportSize2]={"TimeBound"60,"Symbolic"False}
In[]:=
testDistsWithSupportSize2[S_,k_,OptionsPattern[]]:=Do[TimeConstrained[estimateAlpha[S,k,"Symbolic"OptionValue["Symbolic"],"Support"support],OptionValue["TimeBound"]],{support,Subsets[Range[0,k],{2}]}]
testDistsWithSupportSize2[{3},4,"Symbolic"True]
testDistsWithSupportSize2[{3,5},5,"Symbolic"True]
Miscellanea
Miscellanea
Proof of uniqueness for the S = {3}, k = 3 case
Proof of uniqueness for the S = {3}, k = 3 case
In[]:=
Minimize[{lambda[{3},3,{p0,p1,p2,p3},(1/3)p1+(2/3)p2+p3]/gamma[{3},3,{p0,p1,p2,p3}],p0+p1+p2+p31,{p0,p1,p2,p3}≥0},{p0,p1,p2,p3}]
In[]:=
Reduce[{lambda[{3},3,{p0,p1,p2,p3},(1/3)p1+(2/3)p2+p3]/gamma[{3},3,{p0,p1,p2,p3}]2/9,p0+p1+p2+p31,{p0,p1,p2,p3}≥0},{p0,p1,p2,p3}]
Limit as k -> infinity of approximability for kAND
Limit as k -> infinity of approximability for kAND
In[]:=
Limit[((k-1)*(k+1)/(4k^2))^((k-1)/2)/2^(-(k-1)),kInfinity]
Limit as k -> infinity of approximability for S = {k - 1, k}, k even
Limit as k -> infinity of approximability for S = {k - 1, k}, k even
In[]:=
Limit[(k/2)*((k-2)*k/(4(k-1)^2))^((k-2)/2)/((k+1)*2^(-(k-1))),kInfinity]
Insertion-only lower bound for Max-3AND
Insertion-only lower bound for Max-3AND
In[]:=
beta[{3},3,{0,.45,.45,.1}]/gamma[{3},3,{0,.45,.45,.1}]
Tests for lower bound for {(k+1)/2} for odd k between 3 and 51
Tests for lower bound for {(k+1)/2} for odd k between 3 and 51
In[]:=
D1[s_]:=SparseArray[s+11,{k+1}]
In[]:=
D2[s_,t_,k_]:=SparseArray[{s+1(2t-(k+1))/(2*(t-s)),t+1((k+1)-2s)/(2(t-s))},{k+1}]
In[]:=
inequality[S_,k_,DA_,DB_]:=lambda[S,k,DA,p]/gamma[S,k,DA]<=lambda[S,k,DB,p]/gamma[S,k,DB]//Simplify
In[]:=
testInequality[S_,k_,DA_,DB_]:=FindInstance[!inequality[S,k,DA,DB]&&0≤p≤1,p]
In[]:=
distsToTest[k_]:=Join[Flatten[Table[Table[D2[s,t,k],{t,s+1,k}],{s,0,k-1}],1],Table[D1[s],{s,1,k-1}]]
In[]:=
Do[Print[k];Print[Flatten[testInequality[{(k+1)/2},k,D2[0,k,k],#]&/@distsToTest[k]]],{k,3,51,2}]
Cite this as: Noah Singer, "Sketching Approximability of Symmetric Boolean CSPs" from the Notebook Archive (2022), https://notebookarchive.org/2022-03-a5vpzhg
Download
