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

Ran Raz, Amir Yehudayoff

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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, orthogonal formulas, non-canceling formulas, and noise-resistant formulas. One ingredient of our proof is an explicit map that has exponentially small discrepancy for every partition of the input variables into two sets of roughly the same size. We give two additional applications of this explicit map: to extractors construction and to communication complexity.

Original languageEnglish (US)
Pages (from-to)167-190
Number of pages24
JournalJournal of Computer and System Sciences
Issue number1
StatePublished - Jan 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


  • Algebraic complexity
  • Discrepancy
  • Extractors


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

Cite this