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 languageEnglish (US)
Title of host publicationProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Pages273-282
Number of pages10
DOIs
StatePublished - 2008
Externally publishedYes
Event49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States
Duration: Oct 25 2008Oct 28 2008

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

Other

Other49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Country/TerritoryUnited States
CityPhiladelphia, PA
Period10/25/0810/28/08

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors'. Together they form a unique fingerprint.

Cite this