ECCC-Report TR05-044https://eccc.weizmann.ac.il/report/2005/044Comments and Revisions published for TR05-044en-usFri, 15 Apr 2005 19:08:50 +0300
Paper TR05-044
| Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits |
Zeev Dvir,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2005/044In 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.
Fri, 15 Apr 2005 19:08:50 +0300https://eccc.weizmann.ac.il/report/2005/044