Transcript Approximate List-Decoding and Hardness Amplification

Direct-Product testing
Parallel Repetitions
And Foams
Avi Wigderson
IAS
Parallel Repetition of Games
and Periodic Foams
Isoperimetric problem:
Minimize surface area given volume.
One bubble.
Best solution: Sphere
Many bubbles Isoperimetric problem:
Minimize surface area given volume.
Why?
Physics, Chemistry, Engineering, Math…
Best solution?: Consider R3
Lord Kelvin 1873
Optimal…
Wearie-Phelan 1994
Even better
Our Problem
Minimum surface
area of body tiling Rd
with period Zd ?
Volume=1
d=2 area:
Choe’89:
>4
4
Optimal!
Bounds in d dimensions
≤OPT≤
[Kindler,O’Donnell,
≤Rao,Wigderson]
OPT ≤
“Spherical Cubes” exist!
Probabilistic construction!
(simpler analysis [Alon-Klartag])
OPEN: Explicit?
Randomized Rounding
Round points in Rd to points in Zd
such that for every x,y
1.
1
2.
Bound does not depend on d
x y
Spine
Torus
Surface blocking all
cycles that wrap around
Probabilistic construction of spine
Step 1
Randomly construct
B in [0,1)d , which in
expectation satisfies
Step 2
Sample independent
translations of B until
[0,1)d is covered, adding
new boundaries to spine.
B
PCPs & Linear equations over GF(2)
m linear equations: Az = b
in n variables: z1,z2,…,zn
Given (A,b)
1) Does there exist z satisfying all m equations?
Easy – Gaussian elimination
2) Does there exist z satisfying ≥ .9m equations?
NP-hard
3) Does there exist z satisfying ≥ .5m equations?
Easy – YES!
[Hastad] δ>0, it is NP-hard to distinguish (A,b) which
are not (½+δ)-satisfiable, from those (1-δ)-satisfiable!
Linear equations as Games
2n variables:
X1,X2,…,Xn, Y1,Y2,…,Yn
m linear equations:
Xi1 + Yi1 = b1
Xi2 + Yi2 = b2
…..
Xim + Yim = bm
Promise: no setting of the
Xi,Yi satisfy more than
(1-δ)m of all equations
Game G
Draw j  [m] at random
Xij
Yij
Alice
αj
Bob
βj
Check if αj + βj = bj
Pr [YES] ≤ 1-δ
Hardness amplification by
parallel repetition
2n variables:
X1,X2,…,Xn, Y1,Y2,…,Yn
m linear equations:
Xi1 + Yi1 = b1
Xi2 + Yi2 = b2
Game Gk
Draw j1,j2,…jk  [m] at random
Xij1Xij2 Xijk
Alice
Yij1Yij2 Yijk
Bob
…..
Xim + Yim = bm
αj1αj2 αjk
βj1βj2 βjk
Promise: no setting of the
Check if αjt + βjt = bjt t [k]
Xi,Yi satisfy more than
(1-δ)m of all equations
Pr[YES] ≤ (1-δ2)k [Raz,Holenstein,Rao]
[Feige-Kindler-O’Donnell]
Spherical Cubes 
X Pr[YES] ≥ (1-δ2)k
[KORW]Spherical Cubes 
[Raz]
Hardness amplification by
Xi1 + Yi1 = b1
other means?
Xi2 + Yi2 = b2
…..
Pr[YES] ≤ (1-δ2)k [Raz,Holenstein,Rao]
Xim + Yim = bm
Promise: no setting of the Pr[YES] ≥ (1-δ2)k [Raz]
Xi,Yi satisfy more than
Major open question: Is there
(1-δ)m of all equations
Test’ s.t. Pr[YES] ≤ (1-δ)k ?
[Khot] Unique games conjecture
Amplification
Xij1… Xijk
Alice
αj1… αjk
Yij1… Yijk Idea: force each player to answer
consistently - e.g. make Alice
Bob
commit to one assignment of Xi’s
β … β
j1
jk
Test: αjt + βjt = bjt t ?
[Impagliazzo-Kabanets-W]
New Test’ with Pr[YES] ≤ (1-δ)√k
Direct-product testing
Part of
- local testing of codes
- property testing
- discrete rigidity / stability
Related to
- local decoding of codes
- Yao’s XOR lemma
Direct Product: Definition
 For f : U  R, the k -wise direct
product fk : Uk  Rk is
fk (x1,…, xk) = ( f(x1), …, f(xk) ).
[Impagliazzo’02, Trevisan’03]:
TT ( fk )
DP Code
is DP Encoding of TT ( f )
Rate and distance of DP Code are “bad”, but
the code is still very useful in Complexity …
Direct-Product Testing
 Given an oracle C : Uk  Rk
Test makes few queries to C, and
(1) Accept if C = fk.
(2) Reject if C is “far away” from any fk
(2’) [Inverse Thm]
Pr [ Test accepts C ] > 
 C  fk on > t() of inputs.
- Minimize # queries
e.g. 2, 3,.. ?
- Analyze small 
e.g.  < 1/k ,  < exp(-k) ?
- Reduce rate/Derandomize e.g.|C| = poly (|U|) ?
DP Testing History
 Given an oracle C : Uk  Rk, is C¼ gk ?
#queries acc prob 
Goldreich-Safra’00*
20
.99
Dinur-Reingold‘06
2
.99
Dinur-Goldenberg‘08
2
1/kα
Dinur-Goldenberg’08
2
1/k
Impagliazzo-Kabanets-W‘08 3
exp(-kα)
Impagliazzo-Kabanets-W‘08* 2
1/kα
/
*Derandomization
Consistency tests
V-Test
[GS00,FK00,DR06,DG08]
Pick two random k-sets S1 = (B1,A), S2 = (A,B2)
with m = k1/2 common elements A.
Check if C(S1)A = C(S2)A
[DG08]:
B1
S1
B2
A
S2
If V-Test accepts with
probability ² > 1/kα ,
then there is g : U R
s.t. C ¼ gk on at least
²/4 fraction of k-sets.
[IKW09]: Derandomize
[DG08]: V-Test fails for ²<1/k
Z-Test
Pick three random k-sets S1 =(B1, A1), S2=(A1,B2),
S3=(B2, A2) with |A1| = |A2| = m = k1/2.
Check if C(S1)A1= C(S2)A1 and C(S2)B2 = C(S3)B2
B1
S1
B2 A
2
S3
A1
S2
Theorem [IKW09]:
If Z-Test accepts with
probability ² > exp(-kα),
then there is g : U R
s.t. C ¼ gk on at least
²/4 fraction of k-sets.
Proof Ideas
Proof steps
1. Pr [ Test accepts C ] >   structure
2. Structure  local agreement
3. local agreement  global agreement
Agreement: there is g : U R
s.t. C ¼ gk on at least
²/4 fraction of k-sets.
Flowers, cores, petals
Flower: determined by S=(A,B)
Core: A
B
Core values: α=C(A,B)A
Petals: ConsA,B =
{ (A,B’) | C(A,B’)A =α }
In a flower, all petals
agree on core values!
B1
B2
A
B3
B5
[IJKW08]: Flower analysis for
DP-decoding. Symmetry arguments!
B4
V-Test ) Structure
(similar to [FK, DG])
Suppose V-Test accepts with probability ².
ConsA,B = { (A,B’) | C(A,B’)A = C(A,B)A }
(1) Largeness: Many
(²/2) flowers (A,B) have
many (²/2) petals ConsA,B
B1
B
(2) Harmony: In every large
flower, almost all pairs of
overlapping sets in Cons are
almost perfectly consistent.
B5
B2
A
B3
B4
V-Test: Harmony
Almost all B1 = (E,D1) and B2 = (E,D2) in Cons
(with |E|=|A|) satisfy C(A, B1)E  C(A, B2)E
D1
B
A
E

E
A

D2
Proof: Symmetry
between A and E
(few errors in AuE )
Chernoff: ² ¼ exp(-kα)
Implication: Restricted
to Cons, an approx
V-Test on E accepts
almost surely:
Unique Decode!
Harmony ) Local DP
Main Lemma: Assume (A,B) is harmonious. Define
g(x) = Plurality { C(A,B’)x | B’2 Cons & x 2 B’ }
Then C(A,B’)B’ ¼ gk (B’), for almost all B’ 2 Cons
D1
B
x
B’
A
E
D2
Intuition: g = g(A,B) is
the unique (approximate)
decoding of C on Cons(A,B)
Idea: Symmetry arguments.
Largness guarantees that
random selections are
near-uniform.
Challenge: Our analysis gets stuck in ² ¼ exp(-√k)
Can one get ² ¼ exp(-k) ??
Local DP structure across Uk
Field of flowers (Ai,Bi)
B2
For each, gi s.t
C(S) ¼ gik (S) if
S2 Cons(Ai,Bi)
Global g?
B1
A
A1
B3
A
A3
A
A2
B
A
Bi
Ai
From local DP to global DP
Q: How to “glue” local solutions ?
A: If a typical S has two disjoint
large, harmonious A’s
² > 1/kα high probability (2 queries) [DG]
² > exp(-kα)
Z-test (3 queries) [IKW]
Derandomization
DP code whose length is
poly (|U|), instead of |U|k
Inclusion graphs are Samplers
Most lemmas analyze sampling properties
m-subsets

A
k-subsets
elements
of U
S
Cons
x
Subsets: Chernoff bounds – exponential error
Subspaces: Chebychev bounds – polynomial error
Derandomized DP Test
Derandomized DP: U=(Fq)d Encode fk (S),
S subspace of const dimension (as [IJKW08] )

Theorem (Derandomized V-Test):
If derandomized V-Test accepts C with
probability ² > poly(1/k), then there is a
function g : U  R such that C (S) ¼ gk (S)
on poly(²) of subspaces S.


Corollary: Polynomial rate testable DP-code
with [DG] parameters!
Summary
Spherical cubes exist
Power of consistency
Counterexample [DG]
For every x 2 U pick a random gx: U  R
For every k-subset S pick a random x(S) 2 S
Define C(S) = gx(S)(S)
C(S1)A=C(S2)A “iff” x(S1)=x(S2)
V-test passes with high prob:
² = Pr[C(S1)A=C(S2)A] ~ m/k2
No global g if ² < 1/k2
B1
S1
B2
A
S2