# Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors

Ran Raz, Amir Yehudayofft

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

### Abstract

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).

Original language English (US) Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 273-282 10 https://doi.org/10.1109/FOCS.2008.22 Published - Dec 30 2008 Yes 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United StatesDuration: Oct 25 2008 → Oct 28 2008

### Publication series

Name Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 0272-5428

### Other

Other 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 United States Philadelphia, PA 10/25/08 → 10/28/08

### All Science Journal Classification (ASJC) codes

• Computer Science(all)

• ## Cite this

Raz, R., & Yehudayofft, A. (2008). Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 (pp. 273-282).  (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2008.22