Document Open Access Logo

A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates

Authors Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.8.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Swapnam Bajpai
  • Indian Institute of Technology, Bombay, Mumbai, India
Vaibhav Krishan
  • Indian Institute of Technology, Bombay, Mumbai, India
Deepanshu Kush
  • Indian Institute of Technology, Bombay, Mumbai, India
Nutan Limaye
  • Indian Institute of Technology, Bombay, Mumbai, India
Srikanth Srinivasan
  • Department of Mathematics, Indian Institute of Technology Bombay, Mumbai, India

Funding

  • Limaye, Nutan: Funded by Mathematical Research Impact Centric Support (MATRICS), SERB.
  • Srinivasan, Srikanth: Funded by Mathematical Research Impact Centric Support (MATRICS), SERB. Work partially done while visiting the Simons Institute for the Theory of Computing, Berkeley.

Cite As Get BibTex

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, and Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.8

Abstract

We show that there is a zero-error randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time.
Formally, for any constants d,k, there is an epsilon > 0 such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-d circuit C made up of k-PTF gates such that C has size at most n^{1+epsilon}. The algorithm runs in time 2^{n-n^{Omega(epsilon)}}.
Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-k PTF (which is a depth-1 circuit of linear size).
The main new tool is the use of a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into a memoization approach that yields the #SAT algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • SAT
  • Polynomial Threshold Functions
  • Constant-depth Boolean Circuits
  • Linear Decision Trees
  • Zero-error randomized algorithms

Metrics

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

References

  1. Amir Abboud and Karl Bringmann. Tighter Connections Between Formula-SAT and Shaving Logs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 8:1-8:18, 2018. Google Scholar
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 375-388, 2016. Google Scholar
  3. Amir Abboud and Aviad Rubinstein. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 35:1-35:14, 2018. Google Scholar
  4. Paul Beame, Stephen A. Cook, and H. James Hoover. Log Depth Circuits for Division and Related Problems. SIAM J. Comput., 15(4):994-1003, 1986. Google Scholar
  5. Lijie Chen. Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. CoRR, abs/1805.10698, 2018. URL: http://arxiv.org/abs/1805.10698.
  6. Ruiwen Chen and Rahul Santhanam. Improved algorithms for sparse MAX-SAT and MAX-k-CSP. In International Conference on Theory and Applications of Satisfiability Testing, pages 33-45. Springer, 2015. Google Scholar
  7. Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Theory of Computing, 14(9):1-55, 2018. URL: http://dx.doi.org/10.4086/toc.2018.v014a009.
  8. Chao-Kong Chow. On the characterization of threshold functions. In Switching Circuit Theory and Logical Design, 1961. SWCT 1961. Proceedings of the Second Annual Symposium on, pages 34-38. IEEE, 1961. Google Scholar
  9. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. Google Scholar
  10. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider. 0-1 Integer Linear Programming with a Linear Number of Constraints. Electronic Colloquium on Computational Complexity (ECCC), 21:24, 2014. Google Scholar
  11. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput., 26(3):693-707, 1997. Google Scholar
  12. Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider. A satisfiability algorithm for sparse depth two threshold circuits. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 479-488. IEEE, 2013. Google Scholar
  13. Valentine Kabanets, Daniel M Kane, and Zhenjian Lu. A polynomial restriction lemma with applications. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 615-628. ACM, 2017. Google Scholar
  14. Valentine Kabanets and Zhenjian Lu. Satisfiability and Derandomization for Small Polynomial Threshold Circuits. In LIPIcs-Leibniz International Proceedings in Informatics, volume 116, 2018. Google Scholar
  15. Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 355-366. IEEE, 2017. Google Scholar
  16. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016., pages 633-643, 2016. Google Scholar
  17. S Muroga. Threshold logic and its applications. 1971. Google Scholar
  18. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  19. Ryan O'Donnell and Rocco A. Servedio. The Chow Parameters Problem. SIAM J. Comput., 40(1):165-199, 2011. Google Scholar
  20. Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. Journal of the ACM (JACM), 52(3):337-364, 2005. Google Scholar
  21. Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Satisfiability coding lemma. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 566-574. IEEE, 1997. Google Scholar
  22. Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58, pages 82:1-82:16, 2016. Google Scholar
  23. Rahul Santhanam. Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, pages 183-192, 2010. Google Scholar
  24. Srikanth Srinivasan. On improved degree lower bounds for polynomial approximation. In LIPIcs-Leibniz International Proceedings in Informatics, volume 24. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  25. Ryan Williams. A New Algorithm for Optimal Constraint Satisfaction and Its Implications. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pages 1227-1237, 2004. Google Scholar
  26. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 231-240. ACM, 2010. Google Scholar
  27. Ryan Williams. Non-uniform ACC Circuit Lower Bounds. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 115-125. IEEE, 2011. Google Scholar
  28. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664-673, 2014. Google Scholar
  29. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 194-202. ACM, 2014. Google Scholar
  30. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015., pages 17-29, 2015. 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