November 11, 2011
Ryan Williams
IBM Almaden Research Center
Title: Algorithms for Circuits and Circuits for Algorithms
Abstract:
Connections have been recently developed between the existence of non-trivial circuit-analysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies a simple property (such as computing the all-zeroes function) can be used to prove limitations on that circuit class, provided the algorithms run slightly faster than exhaustive search. More precisely, a non-trivial SAT algorithm for a circuit class can be used to find functions computable in nondeterministic exponential time that cannot be computed by that circuit class.
Informally, this connection can be interpreted as saying "good algorithms for circuits imply there are no good circuits for some algorithms." This talk will explore the ideas behind this theme and the potential for further progress.
