ECCC-Report TR13-057https://eccc.weizmann.ac.il/report/2013/057Comments and Revisions published for TR13-057en-usFri, 05 Apr 2013 22:42:48 +0300
Paper TR13-057
| Mining Circuit Lower Bound Proofs for Meta-Algorithms |
Ruiwen Chen,
Valentine Kabanets,
Antonina Kolokolova,
Ronen Shaltiel,
David Zuckerman
https://eccc.weizmann.ac.il/report/2013/057We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit from a known class of circuits, find in deterministic time poly($2^n$) a circuit $C$ (no restriction on the type of $C$) computing $f$ so that the size of $C$ is less than the trivial circuit size $2^n/n$. We get non-trivial compression for functions computable by $AC^0$ circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known.
These compression algorithms rely on the structural characterizations of ``easy'' functions, which are useful both for proving circuit lower bounds and for designing ``meta-algorithms'' (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the ``shrinkage under random restrictions'' results [Sub61,Has98], strengthened to the ``high-probability'' version by [San10,IMZ12,KR12]. We give a new, simple proof of the ``high-probability'' version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about $n^2$. We also use this shrinkage result to get an alternative proof of the recent result by Komargodski and Raz [KR12] of the average-case lower bound against small (de Morgan) formulas.
Finally, we show that the existence of any non-trivial compression algorithm for a circuit class $C\subseteq$P/poly would imply the circuit lower bound that NEXP is not in $C$. This complements Williams's result [Wil10] that any non-trivial Circuit-SAT algorithm for a circuit class $C$ would imply a superpolynomial lower bound against $C$ for a language in NEXP.
Fri, 05 Apr 2013 22:42:48 +0300https://eccc.weizmann.ac.il/report/2013/057