Document Open Access Logo

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

Authors Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.1.pdf
  • Filesize: 0.66 MB
  • 35 pages

Document Identifiers

Author Details

Ruiwen Chen
Rahul Santhanam
Srikanth Srinivasan

Cite As Get BibTex

Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 1:1-1:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.1

Abstract

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is epsilon_d > 0 such that Parity has correlation at most 1/n^{Omega(1)} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{Omega(1)}} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [Impagliazzo/Paturi/Saks, SIAM J. Comp., 1997].

We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-$d$ threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC^0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential-time learning algorithms for AC^0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas ofany depth. 

Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

Subject Classification

Keywords
  • threshold circuit
  • satisfiability algorithm
  • circuit lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), 2008. Google Scholar
  2. Miklos Ajtai. Σ¹₁-formulae on finite structures. Annals of Pure and Applied Logic, 24:1-48, 1983. Google Scholar
  3. James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):135-148, 1994. URL: http://dx.doi.org/10.1007/BF01215346.
  4. László Babai, Noam Nisan, and Mario Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45(2):204-232, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90047-M.
  5. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P =? NP question. SIAM Journal on Computing, 4(4):431-442, 1975. Google Scholar
  6. Richard Beigel. When do extra majority gates help? polylog(N) majority gates are equivalent to one. Computational Complexity, 4:314-324, 1994. URL: http://dx.doi.org/10.1007/BF01263420.
  7. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. Mining circuit lower bound proofs for meta-algorithms. Computational Complexity, 24(2):333-392, 2015. URL: http://dx.doi.org/10.1007/s00037-015-0100-0.
  8. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, New York, USA, 2000. Google Scholar
  9. Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM J. Comput., 39(8):3441-3462, 2010. URL: http://dx.doi.org/10.1137/100783030.
  10. Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, and Li-Yang Tan. Average sensitivity and noise sensitivity of polynomial threshold functions. SIAM J. Comput., 43(1):231-253, 2014. URL: http://dx.doi.org/10.1137/110855223.
  11. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.
  12. W. Feller. An Introduction to Probability Theory and its Applications. John Wiley &Sons, New York, 3 edition, 1968. Google Scholar
  13. Merrick Furst, James Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, April 1984. Google Scholar
  14. Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, and Srikanth Srinivasan. A tail bound for read-k families of functions. Random Struct. Algorithms, 47(1):99-108, 2015. URL: http://dx.doi.org/10.1002/rsa.20532.
  15. Parikshit Gopalan and Rocco A. Servedio. Learning and lower bounds for ac^0 with threshold gates. Electronic Colloquium on Computational Complexity (ECCC), 17:74, 2010. URL: http://eccc.hpi-web.de/report/2010/074.
  16. Craig Gotsman and Nathan Linial. Spectral properties of threshold functions. Combinatorica, 14(1):35-50, 1994. URL: http://dx.doi.org/10.1007/BF01305949.
  17. Kristoffer Arnsfelt Hansen and Peter Bro Miltersen. Some meet-in-the-middle circuit lower bounds. In Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, pages 334-345, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28629-5_24.
  18. Prahladh Harsha, Adam Klivans, and Raghu Meka. Bounding the sensitivity of polynomial threshold functions. Theory of Computing, 10:1-26, 2014. URL: http://theoryofcomputing.org/articles/v010a001/.
  19. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20, 1986. URL: http://dx.doi.org/10.1145/12130.12132.
  20. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC0. In Proceedings of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 961-972, 2012. Google Scholar
  21. Russell Impagliazzo, Mohan Paturi, and Stefan Schneider. A satisfiability algorithm for sparse depth two threshold circuits. In Proceedings of 54th Annual IEEE Symposium on Foundations of Computer Science, pages 479-488, 2013. Google Scholar
  22. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693-707, 1997. URL: http://dx.doi.org/10.1137/S0097539792282965.
  23. Daniel M. Kane. The correct exponent for the gotsman-linial conjecture. Computational Complexity, 23(2):151-175, 2014. URL: http://dx.doi.org/10.1007/s00037-014-0086-z.
  24. Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci., 68(4):808-840, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.002.
  25. Ilan Komargodski and Ran Raz. Average-case lower bounds for formula size. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 171-180, 2013. URL: http://dx.doi.org/10.1145/2488608.2488630.
  26. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform and learnability. Journal of the ACM, 40(3):607-620, 1993. Google Scholar
  27. Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC⁰ circuits with n^ 1-o(1) symmetric gates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 640-651, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0_54.
  28. Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM J. Comput., 42(3):1275-1301, 2013. URL: http://dx.doi.org/10.1137/100811623.
  29. Noam Nisan. The communication compelxity of threshold gates. Combinatorics: Paul Erdös is Eighty, Bolyai Society Mathematical Studies, pages 301-315, 1993. Google Scholar
  30. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  31. Ryan O'Donnell. Hardness amplification within _np. J. Comput. Syst. Sci., 69(1):68-94, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.01.001.
  32. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  33. Ryan O'Donnell and Rocco A. Servedio. The chow parameters problem. SIAM J. Comput., 40(1):165-199, 2011. URL: http://dx.doi.org/10.1137/090756466.
  34. Ramamohan Paturi and Michael E. Saks. Approximating threshold circuits by rational functions. Inf. Comput., 112(2):257-272, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1059.
  35. Yuval Peres. Noise stability of weighted majority, December 19 2004. Comment: six pages. URL: http://arxiv.org/abs/math/0412377.
  36. Vladimir V. Podolskii. Exponential lower bound for bounded depth circuits with few threshold gates. Inf. Process. Lett., 112(7):267-271, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2011.12.011.
  37. Anup Rao. Extractors for low-weight affine sources. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 95-101, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.36.
  38. Alexander Razborov. Lower bounds on the size of bounded-depth networks over the complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  39. Alexander Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  40. Alexander A. Razborov and Avi Wigderson. n^omega(log n) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inf. Process. Lett., 45(6):303-307, 1993. URL: http://dx.doi.org/10.1016/0020-0190(93)90041-7.
  41. Michael E. Saks. Slicing the hypercube. Surveys in Combinatorics, 1993, pages 211-255, 1993. URL: http://dl.acm.org/citation.cfm?id=164558.164579.
  42. Rahul Santhanam. Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In Proceedings of 51st Annual IEEE Symposium on Foundations of Computer Science, pages 183-192, 2010. Google Scholar
  43. Rocco A. Servedio. Every linear threshold function has a low-weight approximator. Computational Complexity, 16(2):180-209, 2007. URL: http://dx.doi.org/10.1007/s00037-007-0228-7.
  44. Alexander A. Sherstov. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica, 33(1):73-96, 2013. URL: http://dx.doi.org/10.1007/s00493-013-2759-7.
  45. Kai-Yeung Siu, Vwani P. Roychowdhury, and Thomas Kailath. Rational approximation techniques for analysis of neural networks. IEEE Transactions on Information Theory, 40(2):455-466, 1994. URL: http://dx.doi.org/10.1109/18.312168.
  46. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the 19th Annual Symposium on Theory of Computing, pages 77-82, 1987. Google Scholar
  47. Ryan Williams. Non-uniform ACC circuit lower bounds. In Proceedings of 26th Annual IEEE Conference on Computational Complexity, pages 115-125, 2011. Google Scholar
  48. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 194-202, 2014. URL: http://dx.doi.org/10.1145/2591796.2591858.
  49. Andrew Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of 26th Annual IEEE Symposium on Foundations of Computer Science, pages 1-10, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact