The polynomial method in circuit complexity
| Author(s) : | Richard Beigel, |
| Publisher : | N/A |
| Publication Date : | 1993 |
| ISSN : | N/A |
| Abstract : | The representation of functions as low-degree polynomials over various rings has provided many insights in the theory of small-depth circuits. We survey some of the closure properties, upper bounds, and lower bounds obtained via this approach. 1., |