Title :
The polynomial method in circuit complexity
Author_Institution :
Maryland Univ., College Park, MD, USA
Abstract :
The basic techniques for using polynomials in complexity theory are examined, emphasizing intuition at the expense of formality. The focus is on the connections to constant-depth circuits, at the expense of polynomial-time Turing machines. The closure properties, upper bounds, and lower bounds obtained by this approach are surveyed
Keywords :
Turing machines; computational complexity; polynomials; circuit complexity; closure properties; constant-depth circuits; formality; lower bounds; polynomial method; polynomial-time Turing machines; upper bounds; Boolean functions; Circuits; Complexity theory; Computer science; Fans; History; Polynomials; Turing machines; Upper bound;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336538
