2026-07-23T06:52:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10101 2024-03-06T10:45:23Z ddc:004 open_access

A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates Bajpai, Swapnam Krishan, Vaibhav Kush, Deepanshu Limaye, Nutan Srinivasan, Srikanth SAT Polynomial Threshold Functions Constant-depth Boolean Circuits Linear Decision Trees Zero-error randomized algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swapnam Bajpai and Vaibhav Krishan and Deepanshu Kush and Nutan Limaye and Srikanth Srinivasan 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.8 urn:nbn:de:0030-drops-101010 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode