Self-Improvement for Circuit-Analysis Problems
Abstract: Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a “self-improving” (or “bootstrapping”) theorem for Circuit-SAT, #Circuit-SAT, and its fully-quantified version: solving one of these problems faster for “large” circuit sizes implies a significant speed-up for “smaller” circuit sizes. Our general arguments work for a variety of models solving circuit-analysis problems, including non-uniform circuits and randomized models of computation.
We derive striking consequences for the complexities of these problems. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply *subexponential-time* algorithms for Circuit-SAT on 2^{o(n)}-size circuits, refuting the Exponential Time Hypothesis. We also show how slightly faster #Circuit-SAT algorithms on large circuits can be used to prove lower bounds against uniform circuits with symmetric gates for functions in deterministic linear time. Our result suggests an “algorithmic method” approach for uniform circuit lower bounds, which trades non-uniformity for a substantial reduction in the complexity of the hard function.
Bio: Ryan Williams is a Professor at MIT in the Department of Electrical Engineering and Computer Science. He got his PhD from CMU under Manuel Blum, and was subsequently a Research Fellow at IBM Research, an Assistant Professor at Stanford, and an Associate Professor at MIT. He works in the design and analysis of efficient algorithms and computational complexity. He is especially interested in relationships between the existence of non-trivial algorithms and proofs of complexity lower bounds. He is also interested in theoretical topics that help give scientific explanations for computational phenomena, such as the unreasonable effectiveness of SAT solvers in practice. He showed among other things that NEXP is not contained in ACC0 (CCC 2011, best paper).