#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

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 [24, 38]. 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 ACC0 ◦ 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.