Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Circuit size lower bounds and #SAT upper bounds through a general framework. / Golovnev, Alexander; Kulikov, Alexander S.; Smal, Alexander V.; Tamaki, Suguru.
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. ed. / Anca Muscholl; Piotr Faliszewski; Rolf Niedermeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 45 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 58).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Circuit size lower bounds and #SAT upper bounds through a general framework
AU - Golovnev, Alexander
AU - Kulikov, Alexander S.
AU - Smal, Alexander V.
AU - Tamaki, Suguru
PY - 2016/8/1
Y1 - 2016/8/1
N2 - Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function. In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: A class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: By going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: Average case lower bounds of 3.24n and 2.59n for circuits over U2 and B2, respectively (though the lower bound for the basis B2is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2n #SAT-algorithms for circuits over U2 and B2of size at most 3.24n and 2.99n, respectively. Here by B2 we mean the set of all bivariate Boolean functions, and by U2the set of all bivariate Boolean functions except for parity and its complement.
AB - Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function. In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: A class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: By going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: Average case lower bounds of 3.24n and 2.59n for circuits over U2 and B2, respectively (though the lower bound for the basis B2is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2n #SAT-algorithms for circuits over U2 and B2of size at most 3.24n and 2.99n, respectively. Here by B2 we mean the set of all bivariate Boolean functions, and by U2the set of all bivariate Boolean functions except for parity and its complement.
KW - Circuit complexity
KW - Exponential time algorithms
KW - Lower bounds
KW - Satisfiability
UR - http://www.scopus.com/inward/record.url?scp=85012883220&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2016.45
DO - 10.4230/LIPIcs.MFCS.2016.45
M3 - Conference contribution
AN - SCOPUS:85012883220
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
A2 - Muscholl, Anca
A2 - Faliszewski, Piotr
A2 - Niedermeier, Rolf
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Y2 - 22 August 2016 through 26 August 2016
ER -
ID: 49823639