TY - GEN
T1 - Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
AU - Raz, Ran
AU - Yehudayofft, Amir
N1 - Funding Information: E-mail addresses: [email protected] (R. Raz), [email protected] (A. Yehudayoff). 1 Research supported by grants from the Binational Science Foundation (BSF), the Israel Science Foundation (ISF), and the Minerva Foundation. 2 Research supported by grants from the Binational Science Foundation (BSF), the Israel Science Foundation (ISF), the Minerva Foundation, and the Israel Ministry of Science (IMOS) – Eshkol Fellowship.
PY - 2008
Y1 - 2008
N2 - We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients' vector of a polynomial and the coefficients' vector of any product of two polynomials with disjoint sets of variables. We prove lower bounds for several old and new subclasses of circuits. Monotone Circuits: We prove a tight 2Ω(n) lower bound for the size of monotone arithmetic circuits. The highest previous lower bound was 2Ω(√n). Orthogonal Formulas: We prove a tight 2 Ω(n) lower bound for the size of orthogonal multilinear formulas (defined, motivated, and studied by Aaronson). Previously, nontrivial lower bounds were only known for subclasses of orthogonal multilinear formulas. Non-Cancelling Formulas: We define and study the new model of non-cancelling multilinear formulas. Roughly speaking, in this model one is not allowed to sum two polynomials that almost cancel each other. The non-cancelling multilinear model is a generalization of both the monotone model and the orthogonal model. We prove lower bounds of nΩ(1) for the depth of non-cancelling multilinear formulas. Noise-Resistant Formulas: We define and study the new model of noise-resistant multilinear formulas. Roughly speaking, noise-resistant formulas are formulas that compute the required polynomial even in the presence of noise. We prove lower bounds of nΩ(1) for the depth of noise-resistant multilinear formulas. One ingredient of our proof is an explicit map f : {0,1}n → {0,1} that has exponentially small discrepancy for every partition of {1,..., n} into two sets of roughly the same size. We give two additional applications of this property to extractors construction and to communication complexity. Mixed-Source Extractors: A mixed-2-source is a source of randomness whose bits arrive from two independent sources (of size n/2 each), but they arrive in a fixed but unknown order. We are able to extract a linear number of almost perfect random bits from such sources. Communication Complexity: We prove a tight Ω(n) lower bound for the randomized best-partition communication complexity off. The best lower bound previously known for this model is Ω(√n).
AB - We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients' vector of a polynomial and the coefficients' vector of any product of two polynomials with disjoint sets of variables. We prove lower bounds for several old and new subclasses of circuits. Monotone Circuits: We prove a tight 2Ω(n) lower bound for the size of monotone arithmetic circuits. The highest previous lower bound was 2Ω(√n). Orthogonal Formulas: We prove a tight 2 Ω(n) lower bound for the size of orthogonal multilinear formulas (defined, motivated, and studied by Aaronson). Previously, nontrivial lower bounds were only known for subclasses of orthogonal multilinear formulas. Non-Cancelling Formulas: We define and study the new model of non-cancelling multilinear formulas. Roughly speaking, in this model one is not allowed to sum two polynomials that almost cancel each other. The non-cancelling multilinear model is a generalization of both the monotone model and the orthogonal model. We prove lower bounds of nΩ(1) for the depth of non-cancelling multilinear formulas. Noise-Resistant Formulas: We define and study the new model of noise-resistant multilinear formulas. Roughly speaking, noise-resistant formulas are formulas that compute the required polynomial even in the presence of noise. We prove lower bounds of nΩ(1) for the depth of noise-resistant multilinear formulas. One ingredient of our proof is an explicit map f : {0,1}n → {0,1} that has exponentially small discrepancy for every partition of {1,..., n} into two sets of roughly the same size. We give two additional applications of this property to extractors construction and to communication complexity. Mixed-Source Extractors: A mixed-2-source is a source of randomness whose bits arrive from two independent sources (of size n/2 each), but they arrive in a fixed but unknown order. We are able to extract a linear number of almost perfect random bits from such sources. Communication Complexity: We prove a tight Ω(n) lower bound for the randomized best-partition communication complexity off. The best lower bound previously known for this model is Ω(√n).
UR - http://www.scopus.com/inward/record.url?scp=57949089733&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57949089733&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2008.22
DO - 10.1109/FOCS.2008.22
M3 - Conference contribution
SN - 9780769534367
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 273
EP - 282
BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Y2 - 25 October 2008 through 28 October 2008
ER -