Abstract
We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size \(3n - n^{0.51}\), the correlation with Parity is at most \(2^{-n^{\varOmega (1)}}\), and there is a #SAT algorithm running in time \(2^{n-n^{\varOmega (1)}}\); for circuit size 2.99n, the correlation with Parity is at most \(2^{-{\varOmega (n)}}\), and there is a #SAT algorithm running in time \(2^{n-{\varOmega (n)}}\). Similar correlation bounds and algorithms are also proved for circuits of size almost 2.5n over the full binary basis \(B_2\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. JACM 48(4), 778–797 (2001)
Beame, P., Impagliazzo, R., Srinivasan, S.: Approximating \(ac^0\) by small height decision trees and a deterministic algorithm for #\(ac^0\) sat. In: Proceedings of the 2012 IEEE Conference on Computational Complexity, CCC 2012 (2012)
Blum, N.: A Boolean function requiring \(3n\) network size. Theoretical Computer Science 28, 337–345 (1984)
Bourgain, J.: On the construction of affine-source extractors. Geometric and Functional Analysis 17(1), 33–57 (2007)
Chen, R., Kabanets, V.: Correlation bounds and #sat algorithms for small linear-size circuits. ECCC 21, 184 (2014)
Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. In: CCC 2014 (2014)
Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small de Morgan formulas. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 165–176. Springer, Heidelberg (2014)
Cohen, G., Shinkar, I.: The complexity of DNF of parities. ECCC 21, 99 (2014)
Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n \(-\) o(n) lower bound on the circuit complexity of affine dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 256–265. Springer, Heidelberg (2011)
Håstad, J.: Almost optimal lower bounds for small depth circuits. In: STOC 1986, pp. 6–20 (1986)
Håstad, J.: The shrinkage exponent of de Morgan formulae is 2. SIAM Journal on Computing 27, 48–64 (1998)
Håstad, J.: On the correlation of parity and small-depth circuits. ECCC 19, 137 (2012)
Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC\(^0\). In: SODA 2012, pp. 961–972 (2012)
Impagliazzo, R., Meka, R., Zuckerman, D.: Pseudorandomness from shrinkage. In: FOCS 2012, pp. 111–119 (2012)
Iwama, K., Morizumi, H.: An explicit lower bound of \(5n - o(n)\) for boolean circuits. In: MFCS 2002, pp. 353–364 (2002)
Komargodski, I., Raz, R.: Average-case lower bounds for formula size. In: STOC 2013, pp. 171–180 (2013)
Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for demorgan formula size. In: FOCS 2013, pp. 588–597 (2013)
Lachish, O., Raz, R.: Explicit lower bound of \(4.5n - o(n)\) for boolena circuits. In: STOC 2001, pp. 399–408. ACM, New York (2001)
Li, X.: A new approach to affine extractors and dispersers. In: CCC 2011, pp. 137–147 (2011)
Nurk, S.: An \(o(2^{0.4058m})\) upper bound for circuit sat. PDMI Preprint (2009)
Reichardt, B.: Reflections for quantum query algorithms. In: SODA 2011, pp. 560–569 (2011)
Santhanam, R.: Fighting perebor: new and improved algorithms for formula and qbf satisfiability. In: FOCS 2010, pp. 183–192 (2010)
Schnorr, C.: Zwei lineare untere schranken für die komplexität boolescher funktionen. Computing 13(2), 155–171 (1974)
Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. In: CCC 2012, pp. 107–116 (2012)
Subbotovskaya, B.A.: Realizations of linear functions by formulas using and or, not. Soviet Math. Doklady 2, 110–112 (1961)
Yao, A.C.: Separating the polynomial-time hierarchy by oracles. In: FOCS 1985, pp. 1–10 (1985)
Yehudayoff, A.: Affine extractors over prime fields. Combinatorica 31(2), 245–256 (2011)
Zwick, U.: A 4n lower bound on the combinational complexity of certain symmetric boolean functions over the basis of unate dyadic boolean functions. SIAM J. Comput. 20(3), 499–505 (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, R., Kabanets, V. (2015). Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)