ECCC-Report TR23-082https://eccc.weizmann.ac.il/report/2023/082Comments and Revisions published for TR23-082en-usSun, 31 Mar 2024 20:59:47 +0300
Revision 1
| Self-Improvement for Circuit-Analysis Problems |
Ryan Williams
https://eccc.weizmann.ac.il/report/2023/082#revision1Many 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.Sun, 31 Mar 2024 20:59:47 +0300https://eccc.weizmann.ac.il/report/2023/082#revision1
Paper TR23-082
| Self-Improvement for Circuit-Analysis Problems |
Ryan Williams
https://eccc.weizmann.ac.il/report/2023/082Many 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.Thu, 01 Jun 2023 17:41:12 +0300https://eccc.weizmann.ac.il/report/2023/082