2026-07-25T02:44:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24174 2025-11-12T13:34:05Z ddc:004 open_access

#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank Limaye, Nutan Srinivasan, Adarsh Srinivasan, Srikanth probabilistic polynomials probabilistic rank circuit satisfiability circuit lower bounds polynomial method threshold circuits There is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time [Ramamohan Paturi et al., 1997; Ryan Williams, 2014]. For circuits with threshold gates, there are several such algorithms based on either - Probabilistic Representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or - Low rank, which allows for an efficient reduction to rectangular matrix multiplication. In this paper, we use a related notion of probabilistic rank to obtain satisfiability algorithms for circuit classes contained in ACC⁰∘3-PTF, i.e. constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions. Even for the special case of a single 3-PTF, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nutan Limaye and Adarsh Srinivasan and Srikanth Srinivasan 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.67 urn:nbn:de:0030-drops-241744 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.67 eng https://creativecommons.org/licenses/by/4.0/legalcode