Paper Info
Title
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
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 LDCs and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results: (1) We show that if $E: \mathbb{F}^n \mapsto \mathbb{F}^m$ is a linear LDC with two queries, then $m = \exp(\Omega(n))$. Previously this was known only for fields of size $\ll 2^n$ [O. Goldreich &etal;, Comput. Complexity, 15 (2006), pp. 263-296]. (2) We show that from every depth 3 arithmetic circuit ($\Sigma\Pi\Sigma$ circuit), ${\cal C}$, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct an LDC. More formally, assume that ${\cal C}$ is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). Denote by $d$ the degree of the polynomial computed by ${\cal C}$ and by $r$ the rank of the linear functions appearing in ${\cal C}$. Then we can construct a linear LDC with two queries that encodes messages of length $r/{\operatorname{polylog}(d)}$ by codewords of length $O(d)$. (3) We prove a structural theorem for $\Sigma\Pi\Sigma$ circuits, with a bounded top fan-in, that compute the zero polynomial. In particular we show that if such a circuit is simple, minimal, and of polynomial size, then its rank, $r$, is only polylogarithmic in the number of variables (a priori it could have been linear). (4) We give new PIT algorithms for $\Sigma\Pi\Sigma$ circuits with a bounded top fan-in: (a) a deterministic algorithm that runs in quasipolynomial time, and (b) a randomized algorithm that runs in polynomial time and uses only a polylogarithmic number of random bits. Moreover, when the circuit is multilinear, our deterministic algorithm runs in polynomial time. Previously deterministic subexponential time algorithms for PIT in bounded depth circuits were known only for depth 2 circuits (in the black box model) [D. Grigoriev, M. Karpinski, and M. F. Singer, SIAM J. Comput., 19 (1990), pp. 1059-1063; M. Ben-Or and P. Tiwari, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1988, pp. 301-309; A. R. Klivans and D. Spielman, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 216-223]. In particular, for the special case of depth 3 circuits with three multiplication gates our result resolves an open question asked by Klivans and Spielman.
Year
DOI
Venue
2007
10.1137/05063605X
SIAM J. Comput.
Keywords
Field
DocType
acm press,linear function,cal c,deterministic algorithm,decodable codes,annual acm symposium,polynomial time,polynomial identity testing,bounded top fan-in,linear ldc,zero polynomial,locally decodable code,computational complexity,randomized algorithm
Polynomial identity testing,Randomized algorithm,Discrete mathematics,Combinatorics,Polynomial,Deterministic algorithm,Linear function,Time complexity,Multilinear map,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
36
5
0097-5397
Citations 
PageRank 
References 
61
1.68
37
Authors
2
Name
Order
Citations
PageRank
Zeev Dvir143730.85
Amir Shpilka2109564.27