Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-082 | 1st June 2023 17:36

Self-Improvement for Circuit-Analysis Problems



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.

ISSN 1433-8092 | Imprint