Affordable Access

The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)

Publication Date
Dagstuhl Research Online Publication Server
  • Algorithm Design, Circuit Complexity, Polynomial Method
  • Data Processing Computer Science
External links


In circuit complexity, the polynomial method is a general approach to proving circuit lower bounds in restricted settings. One shows that functions computed by sufficiently restricted circuits are "correlated" in some way with a low-complexity polynomial, where complexity may be measured by the degree of the polynomial or the number of monomials. Then, results limiting the capabilities of low-complexity polynomials are extended to the restricted circuits. Old theorems proved by this method have recently found interesting applications to the design of algorithms for basic problems in the theory of computing. This paper surveys some of these applications, and gives a few new ones.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times