The polynomial method in circuit complexity
Author:
- R. BeigelRBR. Beigel
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 82-95
Abstract
The representation of functions as low-degree polynomials over various ringshas provided many insights in the theory of small-depth circuits. We surveysome of the closure properties, upper bounds, and lower bounds obtained viathis approach.1. IntroductionThere is a long history of using polynomials in order to prove complexity bounds.Minsky and Papert [39] used polynomials to prove early lower bounds on the order ofperceptrons. Razborov [46] and Smolensky [49] used them to prove...Keywords
This publication has 41 references indexed in Scilit:
- The power of the middle bit2003
- PP is closed under truth-table reductions2002
- A survey on counting classes2002
- A Circuit-Based Proof of Toda′s TheoremInformation and Computation, 1993
- Size-depth trade-offs for threshold circuits1993
- SeparatingPH fromPP by relativizationActa Mathematica Sinica, English Series, 1992
- Relations among mod-classesTheoretical Computer Science, 1990
- Constant depth circuits, Fourier transform, and learnability1989
- Almost optimal lower bounds for small depth circuits1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984