Analysis Of PCPP System For Testing Proximity To RS,=

in this Mathematica notebook we provide additional details regarding our Theorem 3
in particular, this file can let you:
- compare asymptotic versus numerical soundness for any (valid) parameter choice of our construction
- compute the concrete-efficiency threshold of the proximity tester in [BSS08] vs. our proximity tester, for ANY choice of cost function
(for questions, email alexch@mit.edu)

Parameter Constraints:

not all parameter choices of our PCPP system are valid
here we give functions that will let us choose only valid parameter choices

CheckIfParamsAreValid[k0_,η_,μ_,γ_]:=
(Min[Floor[((k0+1)/2)]-γ,Ceiling[((k0+1)/2)]+γ]≥1)&&(Max[Floor[((k0+1)/2)]-γ+μ+1,Ceiling[((k0+1)/2)]+γ]< k0+1)&&(Min[Floor[((k0+1)/2)]-γ+μ+1,Ceiling[((k0+1)/2)]+γ]≥  η+1)&&(k0+((3+(((-1))^(Mod[k0,2])))/2)>Floor[((k0+((3+(((-1))^(Mod[k0,2])))/2))/2)]-γ+μ+1)&&(k0+((1+(((-1))^(Mod[k0,2])))/2)>Ceiling[((k0+((1+(((-1))^(Mod[k0,2])))/2))/2)]+γ)&&(μ+1≥η)&&(η≥Max[2,μ+1]) &&(μ≥ γ)
ValidGammas[k0_,η_,μ_]:= DeleteCases[DeleteDuplicates[Table[If[CheckIfParamsAreValid[k0,η,μ,γ],γ,-1],{γ,0,Floor[((k0+1)/2)]-1}]],-1]

Dimensions And Sizes Of Subspaces:

our PCPP system is recursive in the sense that it reduces proximity testing over a certain subspace over smaller subspaces, and so on
here we provide functions for the sizes of these subspaces

basisL0[k_,γ_]:=Floor[(k/2)]-γ
L0[k_,γ_]:=(2^(basisL0[k,γ]))
basisL0'[k_,γ_,μ_]:=Floor[(k/2)]-γ+μ
L0'[k_,γ_,μ_]:=(2^(basisL0'[k,γ,μ]))
basisL1[k_,γ_]:=Ceiling[(k/2)]+γ
L1[k_,γ_]:=(2^(basisL1[k,γ]))
basisLβ[k_,γ_,μ_]:=Floor[(k/2)]-γ+μ+1
Lβ[k_,γ_,μ_]:=(2^(basisLβ[k,γ,μ]))

Useful Constants:

we define here some useful constants to be used in the soundness computations

c0[η_]:=(4/(((1-(1/(2^(η-1)))-(1/(2^η))))^2))  
a[η_]:=((2^(η+1))/((2^(η-1))-1))* (1+c0[η])
b[μ_]:=(2^(μ+2))
e[k0_,η_,μ_,γ_] :=Min[Log2[((k0+((3+(((-1))^(Mod[k0,2])))/2))/(Floor[((k0+((3+(((-1))^(Mod[k0,2])))/2))/2)]-γ+μ+1))] , Log2[((k0+((1+(((-1))^(Mod[k0,2])))/2))/(Ceiling[((k0+((1+(((-1))^(Mod[k0,2])))/2))/2)]+γ))]]

Asymptotic Soundness:

our asymptotic soundness analysis shows that V_{RS,=} has soundness function d/k^(log c) for c chosen below

c[k0_,η_,μ_,γ_]:=(((a[η]+((b[μ])/2)+((Sqrt[b[μ]×(b[μ]+4×a[η])])/2)))^(1/(e[k0,η,μ,γ])))

LogCAsymptotic[k0_,η_] := 
If[ValidGammas[k0,η,η-1]=={},
-1,
N[Min[Table[Log2[c[ k0,η,η-1,γ]],{γ,ValidGammas[k0,η,η-1]}]]]
]

Numerical Soundness:

our numerical soundness analysis shows that V_{RS,=} has soundness function d/MinDistanceFunc, so that the ``effective’’ log(c) for a dimension k is log(MinDistanceFunc)/log(k); 
we take here the worst such value for  k=k0,...,100 (i.e., considering problem instances of size up to 2^100)

ATerm[k_,k0_,η_,μ_,γ_] :=((2^η)/((2^(η-1))-1))*Max[2*(1+c0[η])*DistanceFunc[basisLβ[k,γ,μ],k0,η,μ,γ] , c0[η]*DistanceFunc[basisL1[k,γ],k0,η,μ,γ]]
BTerm[k_,k0_,η_,μ_,γ_] := (2^(μ+2))*DistanceFunc[basisLβ[k,γ,μ],k0,η,μ,γ]

DistanceFunc[k_,k0_,η_,μ_,γ_] := DistanceFunc[k,k0,η,μ,γ]=
If[k<=k0,
     1,
     ATerm[k,k0,η,μ,γ]+((BTerm[k,k0,η,μ,γ])/2)+((Sqrt[BTerm[k,k0,η,μ,γ]*(BTerm[k,k0,η,μ,γ]+4*ATerm[k,k0,η,μ,γ])])/2)
]


MinDistanceFunc[k_,k0_,η_] := Min[Table[N[DistanceFunc[k,k0,η,η-1,γ]],{γ,ValidGammas[k0,η,η-1]}]]
LogCNumericalPerDimension[k_,k0_,η_] := If[ValidGammas[k0,η,η-1]=={},
-1,
N[((Log2[MinDistanceFunc[k,k0,η]]  )/(Log2[k]))]
]

MaxRange = 100;

LogCNumerical[k0_,η_]:=NumberForm[Max[Table[LogCNumericalPerDimension[k,k0,η],{k,k0,MaxRange}]],{2,1}]

Comparison Between Asymptotic And Numerical Soundness

Comparing the value of log(c), from asymptotic (in black) and numerical (in blue), for several parameter choices

mink0=2;
maxk0 = 20;
minη = 2;
maxη = 8;

CellFunction[k0_,η_]:=  If[ValidGammas[k0,η,η-1]=={},
Style["n/a",FontColor->Red],
Grid[{{Style[NumberForm[LogCAsymptotic[k0,η],{2,1}],FontColor->Black]},{Style[LogCNumerical[k0,η],FontColor->Blue]}}]
]

FirstRow[mink0_,maxk0_] := Join[{Style["log(c)",Bold]},Table[Style[StringForm["k0=`1`",k0],Bold],{k0,mink0,maxk0}]]

OtherRow[mink0_,maxk0_,η_]:= Join[{Style[StringForm["η=`1`",η],Bold]},Table[CellFunction[k0,η],{k0,mink0,maxk0}]]

Grid[
Join[
{FirstRow[mink0,maxk0]}, 
Table[OtherRow[mink0,maxk0,η],{η,minη,maxη}]
],
Frame->All, ItemSize->{4,4},Alignment->{Center,Center},Background->LightYellow
]

Some representative plots of the asymptotic vs. numerical value of log(c)

CompareAsymptoticAndNumerical[k0_,η_]  := Plot[{LogCAsymptotic[k0,η],LogCNumericalPerDimension[k,k0,η]},{k,k0,MaxRange},AxesOrigin->{0,0}]

Grid[{{CompareAsymptoticAndNumerical[4,3] ,CompareAsymptoticAndNumerical[8,4],CompareAsymptoticAndNumerical[12,5]}}]

Concrete-Efficiency Threshold Computations

Proximity Parameter Of The PCPP System

as per the standard definition, we choose the proximity parameter of the PCPP system to be 1/3
we also give a standard choice of cost function for computing the threshold
one can specify other cost functions

ProximityParameter=1/3;
CostFuction[a_,b_]:=a*b

Length Of Proximity Proof:

this is a function that computes the length of the proximity proof

ProximityProofLength[k_,k0_,η_,μ_,γ_]:=
If[k<=k0,
    0,
    L1[k,γ]×Lβ[k,γ,μ]
 +   L1[k,γ]×ProximityProofLength[basisLβ[k,γ,μ],k0,η,μ,γ]
 +   L0'[k,γ,μ]×ProximityProofLength[basisL1[k,γ],k0,η,μ,γ] 
]

[BSS08] Threshold Analsys:

the last time that BSSDifference becomes positive signals the BSS08 threshold for the given cost function;
using the funcionality below, one can binary search for where this value is;
for the cost function a*b, we find that it is 2^683

BSSc0 = 128;
BSSLogC = N[Log2[(((64*(BSSc0+2/3)))^(1/Log2[8/7]))]];
BSSk0 = 6;
BSSη = 3;
BSSμ = 2;
BSSγ =0;
BSSDifference[k_]:=(2^(k-BSSη)) -CostFuction[(((2^k)+ProximityProofLength[k,BSSk0,BSSη,BSSμ,BSSγ])/(2^(k-BSSη))),((k^BSSLogC)/ProximityParameter)×(2^BSSk0)]
BSSmink=670;
BSSmaxk=690;

Table[{k,If[BSSDifference[k]≥ 0,1,-1]},{k,BSSmink,BSSmaxk}]

Our Threshold Analysis:

the last time that Difference becomes positive signals our threshold for the given cost function;
using the funcionality below, one can find this threshold;
for the cost function a*b, we find that it is 2^43 when choosing eta=3 and k0=15

SoundnessFunction[k_,k0_,η_,μ_,γ_]:=(ProximityParameter/(DistanceFunc[k,k0,η,μ,γ]))
NumRepetitions[k_,k0_,η_,μ_,γ_]:=Ceiling[((-1)/(Log2[1-SoundnessFunction[k,k0,η,μ,γ]]))]

CostWithGamma[k_,k0_,η_,μ_,γ_]:=CostFuction[(2^k)+ProximityProofLength[k,k0,η,μ,γ],NumRepetitions[k,k0,η,μ,γ]×(2^k0)]

Difference[k_,k0_,η_,μ_] := (2^(2k-2η-1))-Min[Table[CostWithGamma[k,k0,η,μ,γ],{γ,ValidGammas[k0,η,μ]} ]]

CostWithGamma[k_,k0_,η_,μ_,γ_]:=CostFuction[(((2^k)+ProximityProofLength[k,k0,η,μ,γ])/(2^(k-η))),NumRepetitions[k,k0,η,μ,γ]×(2^k0)]

Difference[k_,k0_,η_] := (2^(k-η))-Min[Table[CostWithGamma[k,k0,η,η-1,γ],{γ,ValidGammas[k0,η,η-1]} ]]

ThresholdAux[k_,k0_,η_]:=
If[k≤ k0,"none",
If[Difference[k,k0,η]≤ 0,
    k+1,
   ThresholdAux[(k-1),k0,η]]
]

StartDim = 130;

ComputeThreshold[k0_,η_]:=
If[ValidGammas[k0,η,η-1]=={},
Style["n/a",FontColor->Red],
If[Difference[StartDim,k0,η]≤ 0,
"increase StartDim",
ThresholdAux[StartDim,k0,η]
]
]

tmink0=2;
tmaxk0 = 20;
tminη = 2;
tmaxη = 5;

tFirstRow[mink0_,maxk0_] := Join[{Style["log(c)",Bold]},Table[Style[StringForm["k0=`1`",k0],Bold],{k0,tmink0,tmaxk0}]]

tOtherRow[mink0_,maxk0_,η_]:= Join[{Style[StringForm["η=`1`",η],Bold]},Table[ComputeThreshold[k0,η],{k0,tmink0,tmaxk0}]]

Grid[
Join[
{tFirstRow[tmink0,tmaxk0]}, 
Table[tOtherRow[tmink0,tmaxk0,η],{η,tminη,tmaxη}]
],
Frame->All, ItemSize->{4,4},Alignment->{Center,Center},Background->LightYellow
]