Locally Testable Codes and Cayley Graphs Research Overview

Locally Testable Codes and Caylay Graphs Parikshit Gopalan (MSR-SVC) Salil Vadhan (Harvard) Yuan Zhou (CMU)

Locally Testable Codes Local tester for an [n, k, d]2linear code C Queries few coordinates Accepts codewords Rejects words far from the code with high probability [BenSasson-Harsha-Raskhodnikova 05]: A local tester is a distribution D on (low-weight) dual codewords

Locally Testable Codes [Blum-Luby-Rubinfeld 90, Rubinfeld-Sudan 92, Freidl- Sudan 95]: (strong) tester for an [n, k, d]2code Queries coordinates according to D on -smooth: queries each coordinate w.p. Rejects words at distance d w.p. d By definition: must have ; would like = ( ) Pr[Reject] .1 Distance from C 1 d/2

The price of locality? Asymptotically good regime #information bits k = (n), distance d = (n) Are there asymptotically good 3-query LTCs? Existential question proposed by [Goldreich-Sudan 02] Best construction: n=k polylog(k), d = (n) [Dinur 05] Rate-1 regime: let d be a large constant, = (1/d), n How large can k be for an [n, k, d]2 -smooth LTC? BCH: n-k = (d/2) log(n), but not locally testable [BKSSZ 08]: n-k = log(n)log(d) from Reed-Muller Can we have n-k = Od(log(n))?

h F2 Caylay graphs on . h,S) Cay(F2 S ={s1,s2, ,sn} F2 F2 {(x,x+si):x F2 Graph Vertices: Edges: h h h,i [n]} S={e1,e2, ,eh} Hypercube: h = n, We are interested in h < n Definition. S is d-wise independent if every subset T of S, where |T|<d, is linearly independent

h F2 Caylay graphs on . s1 h,S) Cay(F2 S ={s1,s2, ,sn} F2 F2 {(x,x+si):x F2 Graph Vertices: Edges: h s2 s2 h h,i [n]} s1 d-wise independent: Abelian analogue of large girth Cycles occur when edge labels sum to 0 always has 4-cycles Cay(F2 h,S)

h F2 Caylay graphs on . h,S) Cay(F2 S ={s1,s2, ,sn} F2 F2 {(x,x+si):x F2 Graph Vertices: Edges: h h h,i [n]} d-wise independent: Abelian analogue of large girth Cycles occur when edge labels sum to 0 always has 4-cycles non-trivial cycles have length at least d h,S) Cay(F2

h F2 Caylay graphs on . h,S) Cay(F2 S ={s1,s2, ,sn} F2 F2 {(x,x+si):x F2 Graph Vertices: Edges: h h h,i [n]} d-wise independent: Abelian analogue of large girth Cycles occur when edge labels sum to 0 always has 4-cycles non-trivial cycles have length at least d (d/2)-neighborhood of any vertex is isomorphic to B(n, d/2), but the vertex set has dimension h << n h,S) Cay(F2

1- embeddings of graph Embedding f: V(G) Rd has distortion c if for every x, y |f(x) f(y)|1 dG(x, y) c|f(x) f(y)|1 c1(G) = minimum distortion over all embeddings

Our results Theorem. The following are equivalent An [n, k, d]2 code C with a tester of smoothness and soundness A Cayley graph where |S| = n, S is d- wise independent, and the graph has an embedding of distortion / Corollary. There exist asymptotically good strong LTCs iff there exists s.t. |S| = (1+ (1))h S is (h)-wise independent c1(G) = O(1) n-k,S) Cay(F2 1- G=Cay(F2 h,S)

Our results Theorem. The following are equivalent An [n, k, d]2 code C with a tester of smoothness and soundness A Cayley graph where |S| = n, S is d- wise independent, and the graph has an embedding of distortion / Corollary. There exist [n, n-Od(log n), d]2 strong LTCs iff there exists s.t. |S| = 2 d(h) S is d-wise independent c1(G) = O(1) n-k,S) Cay(F2 1- G=Cay(F2 h,S)

The correspondence n-k,S) Cay(F2 , |S|=n, [n, k, d]2 code C: (n-k) x n parity check matrix [s1, s2, , sn] S is d-wise indep. Vertex set: F2n/C, x,x+e1 ), x,x+e2 Edge set: . ( ( ), , x,x+en ( ) y x Claim. Shortest path between and equals the shortest Hamming distance from (x y) to a codeword. 1- To show: the correspondence between embeddings and local testers.

Embeddings from testers Given a tester distribution D on , each a ~ D defines a cut on V(G) = F2n/C an embedding 1- Claim. The embedding has distortion / Proof. Given two nodes and distG(x,y)=wt(x-y) y x d wt(x-y) Pr[(x-y)isrejected] e wt(x-y)

Testers from Embeddings Given embedding distribution D on If D supported on linear functions, we d be (essentially) done. Claim. There is a distribution D on linear functions with distortion as good as D. Proof sketch. Extend f to all points in The Fourier expansion is supported on : n F2 fa ( ) 2 ca When D samples f, D samples w.p.

Applications [Khot-Naor 06]: If has distance (n) and relative rate (1), then c1(G) = (n) where G is the Caylay graph defined by C as described before Proof. Suffices to lowerbound / Since has distance (n), we have = (1) Let t be the covering radius of C, we have 1/t (since the rej. prob. can be t ) t = (n) (since has distance (n)) Therefore / t = (n)

Future directions Can we use this equivalence to prove better constructions (or better lower bounds) for LTCs?

Thanks!