In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword.
Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results: 1. We show an exponential lower bound on the length of locally decodable codes with 2 queries, over arbitrary fields.
Previously such bounds were known for fields of size $<< 2^n$. 2. We show that from every depth 3 arithmetic circuit with a bounded top fan-in, that computes the zero polynomial, one can construct a locally decodable code with 2 queries. 3. As a corollary of the results above we prove a structural theorem for identically zero depth 3 circuits. 4. Using the structural theorem we obtain new PIT algorithms for depth
3 circuits. In particular for such circuits with bounded top fan-in we get - A deterministic algorithm that runs in quasi-polynomial time - A probabilistic algorithm that runs in polynomial time and uses only polylogarithmic number of random bits. In particular for the case of top fan-in = 3 this resolves an open question asked by Klivans and Spielman.
Joint work with Amir Shpilka
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.