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

Ran Raz, Amir Yehudayoff

Research output: Contribution to journalArticle

14 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, 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
Volume77
Issue number1
DOIs
StatePublished - Jan 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Algebraic complexity
  • Discrepancy
  • Extractors

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

  • Cite this