The polynomial method in circuit complexity
- 30 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 8, 82-95
- https://doi.org/10.1109/sct.1993.336538
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 bitPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- PP is closed under truth-table reductionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A survey on counting classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Circuit-Based Proof of Toda′s TheoremInformation and Computation, 1993
- Size-depth trade-offs for threshold circuitsPublished by Association for Computing Machinery (ACM) ,1993
- SeparatingPH fromPP by relativizationActa Mathematica Sinica, English Series, 1992
- Relations among mod-classesTheoretical Computer Science, 1990
- Constant depth circuits, Fourier transform, and learnabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Almost optimal lower bounds for small depth circuitsPublished by Association for Computing Machinery (ACM) ,1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984