Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search.
We prove a \emph{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, in both the fine-grained and parameterized setting. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply \emph{subexponential-time} algorithms for Circuit-SAT on $2^{o(n)}$-size circuits, refuting the Exponential Time Hypothesis. We also show that any algorithm for Circuit-SAT with $k$ inputs and $n$ gates running in $1000000^k + n^{1+\varepsilon}$ time (for all $\varepsilon > 0$) would imply algorithms running in time $(1+\varepsilon)^k + n^{1+\varepsilon}$ time (for all $\varepsilon > 0$), also refuting the Exponential Time Hypothesis. Applying our ideas in the $\#$Circuit-SAT setting, we prove new unconditional lower bounds against uniform circuits with symmetric gates for functions in deterministic linear time.

full version of a paper in STOC'24: minor corrections, added a parameterized complexity version, more discussion of related work

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.