Abstract:

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 prove an exponential lower bound on the length of linear LDC
with 2 queries over arbitrary fields (previously it was known only
for fields of size smaller than $2^n$).

2. We show that from every depth 3 arithmetic circuit C, with a
bounded (constant) top fan-in that computes the zero polynomial, one
can construct an LDC with 2 queries.

3. We prove a structural theorem for depth 3 arithmetic circuits,
with a bounded top fan-in, that compute the zero polynomial.

4. We give new PIT algorithms for depth 3 arithmetic circuits with a
bounded top fan-in.

Joint work with Zeev Dvir