Fixed-Polynomial Size Circuit Bounds.

Lance Fortnow Rahul Santhanam Ryan Williams

Published in: Computational Complexity Conference (2009)

Keyphrases

polynomial size
exponential size
dnf formulas
upper and lower bounds
boolean functions
upper bound
lower bound
knowledge compilation
worst case
lower and upper bounds
bounded treewidth
constraint satisfaction problems
uniform distribution
random instances