$\mathrm{\#}\mathrm{SAT}$-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

Given a family of circuits $𝒞,$ a fundamental algorithmic question one can ask about it is the satisfiability question: does a given $C\in 𝒞$ have a satisfying assignment? This being a canonical $\mathrm{𝖭𝖯}$-complete problem even for very simple $𝒞$, it is hard to imagine a polynomial-time algorithm for this problem. However, it is still reasonable to try to obtain some speed-up over brute-force search. Typically, and also in this paper, we aim for running times of $2^{n-s}$ where $n$ denotes the number of variables and $s$ is the “savings” over brute-force search.¹¹1The trivial algorithm evaluates the circuit on every input, which takes time at least $2^n.$

A long line of work has leveraged structural understanding from complexity-theoretic research on circuit lower bounds to devise satisfiability algorithms for various families of circuits. For example, these ideas have led to approaches to satisfiability algorithms for constant-depth circuit classes [24, 17, 37, 25], Boolean formulas [29, 30] and Threshold circuits of various kinds [34, 12, 18, 9, 7].

A profound result of Williams [36, 38] also makes a connection in the opposite direction, by showing that satisfiability algorithms with savings $\omega (\log n)$ for many “reasonable” circuit classes implies lower bounds for these classes.²²2i.e. a superpolynomial improvement over brute-force This gives even more impetus to studying the satisfiability problem in this regime.

There are a handful of techniques from complexity-theoretic investigations that are useful in devising satisfiability algorithms. These include

• $\mathrm{■}$

  Memoization: In the setting of lower bounds, this idea goes back to the work of Nechiporuk [22] who used it to show quadratic Boolean formula lower bounds. This idea can also be used to obtain satisfiability algorithms in some settings (see e.g. [28, 7]). To apply this technique to a circuit class $𝒞$, one must be able to prove a strong upper bound on the number of functions in $𝒞$ of a given size. Unfortunately, in most algorithmic settings (e.g. CNF formulas of unbounded width), one cannot get a strong enough upper bound of this form to get much out of this technique.

• $\mathrm{■}$

  Restriction-based techniques: A popular family of techniques used to devise satisfiability algorithms is the idea of restricting a subset of the variables (i.e. setting them to Boolean assignments) in a way that simplifies the underlying circuit and allows us to circumvent having to try all settings of the other variables. This leads to DPLL-style algorithms for SAT and their extensions to ${\mathrm{𝖠𝖢}}^0$ circuits [17] and Boolean formulas [29] based on results such as the Håstad Switching Lemma [15, 16]. Unfortunately, these arguments do not extend to circuit classes where the gate set contains gates other than the DeMorgan basis (e.g. XOR gates or Majority gates that count the number of $1$s) unless severe size restrictions are placed on the circuits [12, 18].

This brings us to the topic of this paper, where we study circuits with threshold gates. For an integer $d$, a Polynomial Threshold Function (PTF) of degree $d$ is defined to be a Boolean function $f:{\{0,1\}}^n\to \{0,1\}$ such that there exists a multilinear polynomial $P$ of degree $\le d$ with integer coefficients such that for each $x\in {\{0,1\}}^n$, $f(x)=1$ if and only if $P(x)>0$. We denote by $d\text{-}\mathrm{𝖯𝖳𝖥}$ the class of polynomial threshold functions of degree $d.$ The special case $d=1$ is denoted $\mathrm{𝖫𝖳𝖥}.$

Even the problem of checking if a given $f\in 2\text{-}\mathrm{𝖯𝖳𝖥}$ is satisfiable is an $\mathrm{𝖭𝖯}$-complete problem.³³3Here, the input is given as a polynomial $P$ with integer coefficients that represents $f$ in the sense described above. Further, the problem for $d\text{-}\mathrm{𝖯𝖳𝖥}$ is a considerable generalization of the problem of optimizing a MAX-$d$-CSP over Boolean variables. While we know algorithms for MAX-$2$-CSP with savings $\mathrm{\Omega }(n)$ [35], obtaining such a result even in the case of $3$-CSPs remains an elusive problem. For the best known result for $d\le 4$ see the work of Alman, Chan, and Williams [3].

We will consider algorithms for classes of polynomial-sized circuits using PTF gates (and also other counting gates). In such situations, neither memoization nor restriction-based techniques seem to be useful in devising satisfiability algorithms, except in very special cases (as we will explain below). However, there are some known algorithms that work for such circuit classes. Mostly, they exploit the following ideas.

• $\mathrm{■}$

  Polynomial representations: This is a powerful circuit-analysis technique going back to a foundational circuit lower bound due to Razborov [26, 32] and follow-up results of Yao [39] and Beigel and Tarui [8] which were aimed towards proving bounds for constant-depth circuits with AND, OR, NOT and modular counting gates. Here, it is shown that small circuits from this class can be represented by (sometimes randomized) polynomials. By making this technique algorithmic and using fast polynomial evaluation algorithms, Williams [38] devised the first satisfiability algorithms for these circuits with non-trivial savings, leading also to his breakthrough circuit lower bound for the class ${\mathrm{𝖠𝖢𝖢}}^0.$

• $\mathrm{■}$

  Rank techniques: Another powerful idea is to reduce the problem of checking satisfiability to computing the entries of a low-rank matrix. Typically, this is done by splitting the $n$ variables into two subsets of size $n/2$ and showing that the $2^{n/2}\times 2^{n/2}$-sized matrix obtained by evaluating the given input circuit $C$ on all pairs of inputs $(x,y)\in {\{0,1\}}^{n/2}\times {\{0,1\}}^{n/2}$ is (a simple function of) a low-rank matrix. By using fast algorithms for rectangular matrix multiplication [14, 34], this leads to satisfiability algorithms for classes such as ${\mathrm{𝖠𝖢𝖢}}^0\circ \mathrm{𝖫𝖳𝖥}$.

In this work, we show how to extend these ideas to polynomial threshold functions of degree up to $3$ and generalizations thereof. It is unclear if either of the above techniques can be used directly to obtain non-trivial savings in this setting.⁴⁴4It should be noted that a PTF of degree $d$ has a low-degree polynomial (sign) representation by definition. However, this alone is not enough to devise a satisfiability algorithm. We also need a low-degree polynomial representation for a disjunction of superpolynomially many PTFs, and whether this stronger property holds is unclear. In fact, it seems unlikely [31]. More precisely, we obtain the following results. See Section 2 for definitions.

Even in the case of a single $3\text{-}\mathrm{𝖯𝖳𝖥},$ the running time of our algorithm beats the best-known previous algorithm of [7], which was based on memoization and yielded savings of $\tilde{\mathrm{\Omega }}(n^{1/3}).$ Moreover, as mentioned above, the technique of memoization does not seem to be useful even for simple extensions of this class to, say, conjunctions of polynomially many $3$-PTFs.

As a consequence of our theorem and the algorithmic method of Williams, extended by Murray and Williams [38, 21], we also derive the first lower bound for the circuit class ${\mathrm{𝖠𝖢𝖢}}^0\circ 3\text{-}\mathrm{𝖯𝖳𝖥}.$

The main idea behind our algorithm is similar to the idea used in the work of Alman, Chan and Williams [3] for MAX-4-CSPs. Specifically, we combine the two techniques mentioned above into a probabilistic rank upper bound for the classes of circuits we consider. For simplicity, consider the case when the input is a polynomial $P(z_1,\mathrm{\dots },z_n)$ of degree $3$ representing a $3$-PTF $f$ and we want to know if $f$ is satisfiable.

As above, we split the $n$ Boolean variables of $P$ into two disjoint sets $A=\{1,\mathrm{\dots },n/2\}$ and $B=\{n/2+1,\mathrm{\dots },n\}$ of size $n/2$ and consider the matrix $M_f$ of size $2^{n/2}\times 2^{n/2}$ where the rows and columns are labelled by settings to variables indexed by $A$ and $B$ respectively and

for each $x,y\in {\{0,1\}}^{n/2}.$ Now, while we cannot argue that $M_f$ is low-rank, we can argue that there is a low-rank (roughly $\exp (\tilde{O}(\sqrt{n})\ll 2^{n/2}$) random matrix $𝐌$ that agrees with $M_f$ in each entry w.h.p. To do this, we write

by noting that each monomial in $P$ must have degree at most $1$ either in the variables indexed by $A$ or by $B.$ Partitioning the monomials that have variables in both parts according to choice of this “special” variable gives the decomposition above ($Q$ and $R$ contain the monomials that contain variables indexed by only one of $B$ or $A$ respectively). This type of decomposition is exactly like that obtained by [3]. From this point on our proof outline is also quite similar. The main place where we differ is that we need to handle weights which are not necessarily polynomially bounded.

We continue as follows. Note that $f(x,y)$ can be written as the sign of the above expression. To express $M_f$ as a low-rank matrix (probabilistically), we use constructions of probabilistic polynomials (see definition in Section 2) for the Majority function⁵⁵5This idea works when the coefficients of the underlying polynomial $P$ are all polynomially small. Our algorithm can also handle coefficients that are exponentially large. In this case, we need some additional circuitry to simulate the sum efficiently. This can be converted to a low-degree polynomial using the construction of Razborov [26, 25]. and variants [6, 3] which allows us to write the above as a random polynomial of degree at most $\tilde{O}(\sqrt{n})$ over the bits of the numbers

Each monomial in the polynomial defines a rank-$1$ matrix, as it is a product of the form $F(x)\cdot G(y)$ for some functions $F$ and $G$. A polynomial of degree $\tilde{O}(\sqrt{n})$ thus defines a matrix of rank $\exp (\tilde{O}(\sqrt{n})).$

To extend the above to (say) ${\mathrm{𝖠𝖢𝖢}}^0\circ 3\text{-}\mathrm{𝖯𝖳𝖥},$ we compose the above construction with standard low-degree polynomial representations of the class ${\mathrm{𝖠𝖢𝖢}}^0$ [2, 8].

This structural result shows that the family of degree-$3$ PTFs has low probabilistic rank. This may be of independent interest. Alman and Williams [5] proved such a result for the inner product function, resulting in improved bounds on the rigidity of the Hadamard matrix. Follow-up results have used this idea to give better circuits for computing the Walsh-Hadamard transform [4].

For the satisfiability algorithm, we need to combine this idea with the standard “blow-up trick” of Williams. Returning to the case of a single $3$-PTF $f(z_1,\mathrm{\dots },z_n),$ we will apply the above idea to

(Note that $g$ is satisfiable if and only if $f$ is satisfiable.) For suitably small $\mathrm{\ell }$ (roughly $\sqrt{n}$), we will apply the above idea to $g$ and show that the analogous matrix $M_g$ has low-rank. By using Coppersmith’s rectangular matrix multiplication algorithm [14, 34], it follows that $M_g$ can be computed in time approximately $2^{n-\mathrm{\ell }}$, leading to savings $\mathrm{\ell }$ for our algorithm.

Finally, to count the number of satisfying assignments, we replace the OR above by a sum and use similar ideas (as in [34, 25]).

Over the past decade, there have been many works studying satisfiability algorithms for circuits using threshold gates and modular counting gates.

In the setting of ${\mathrm{𝖠𝖢𝖢}}^0$, the class of constant-depth circuits using AND, OR, NOT and modular counting gates, the first non-trivial satisfiability algorithms were given by Williams [38] followed by improvements in [34], which also yields algorithms for the class ${\mathrm{𝖠𝖢𝖢}}^0\circ \mathrm{𝖫𝖳𝖥}.$ Further extensions have been obtained by works of [3, 11] but neither of these works allow us to replace the LTF gates by PTFs of higher degree.

For a single $d\text{-}\mathrm{𝖯𝖳𝖥}$, the best known algorithms use the memoization technique and have savings $\tilde{\mathrm{\Omega }}(n^{1/d}).$ [27, 7] This technique is grounded in the fact that the number of degree-$d$ PTFs on $n$ variables is $2^{O(n^{d+1})}$ [13], and this does not extend even to simple combinations of PTFs, such as conjunctions of polynomially many PTFs (or even LTFs).⁶⁶6For example, it is easy to show that the number of distinct functions that can be written as a conjunction of $s$ LTFs is always at least $2^s$ as long as $n>\log s.$

There are also restriction-based satisfiability algorithms for circuits made up of LTF and, more generally, PTF gates [12, 18]. Unfortunately, though, these algorithms only work when the size of the circuits (defined in terms of the number of wires) is slightly superlinear in the number of variables.

In Section 3, we upper bound the probabilistic rank of $3\text{-}\mathrm{𝖯𝖳𝖥}$s (Lemma 14) and present a deterministic $\mathrm{\#}$SAT algorithm for ${\mathrm{𝖠𝖢}}^0[{\mathrm{𝖬𝖮𝖣}}_p]\circ 3\text{-}\mathrm{𝖯𝖳𝖥}$ circuits (Theorem 17). In Section 4, we present a $\mathrm{\#}$SAT algorithm for ${\mathrm{𝖠𝖢𝖢}}^0\circ 3\text{-}\mathrm{𝖯𝖳𝖥}$ circuits (Theorem 20).

All our algorithms can be implemented in the standard RAM model. The notations $\mathrm{poly}(n),\mathrm{polylog}(n)$ are used to denote arbitrary, but fixed polynomial and polylogarithmic factors in $n$ respectively. We use the $O^{\ast }(\cdot )$ and $\tilde{O}(\cdot )$ notation to suppress polynomial and logarithmic factors respectively.

A polynomial threshold function can be defined using multiple polynomials. Hence, the number of bits needed to represent a $\mathrm{𝖯𝖳𝖥}$ depends on the bit complexity of the polynomial used to define it.

It is known that any $d\text{-}\mathrm{𝖯𝖳𝖥}$ can be represented using a polynomial with bit complexity upper bounded by $O(n^d\log n)$ [20]. However, given an arbitrary $d\text{-}\mathrm{𝖯𝖳𝖥}$, it is not clear how to efficiently obtain such a low weight representation. Nevertheless, our algorithms in Section 3 can handle $\mathrm{𝖯𝖳𝖥}$’s represented by polynomials with bit complexity up to $2^{n^{\delta }}$, for some fixed $\delta >0$. For the purpose of proving lower bounds, we can always assume that the bit complexity of $d\text{-}\mathrm{𝖯𝖳𝖥}$ functions is upper bounded by $O(n^d\log n)$.

We use the standard definitions for boolean circuits and circuit classes. We refer the reader to [33] for more details. The size of a circuit is defined to be the number of wires and its depth is defined to be the total number of layers. The circuit class ${\mathrm{𝖠𝖢}}^0$ consists of constant depth circuits with $\mathrm{𝖠𝖭𝖣},\mathrm{𝖮𝖱},\mathrm{𝖭𝖮𝖳}$ gates of unbounded fan-in. For any $m\in \mathbb{N}$, a ${\mathrm{𝖬𝖮𝖣}}_m$ gate with fan-in $t$ outputs $1$ if the sum (over $\mathbb{N}$) of its inputs is divisible by $m$ and outputs $0$ otherwise. For any prime $p$, the class ${\mathrm{𝖠𝖢}}^0[{\mathrm{𝖬𝖮𝖣}}_p]$ consists of circuits with $\mathrm{𝖠𝖭𝖣},\mathrm{𝖮𝖱},\mathrm{𝖭𝖮𝖳}$ and ${\mathrm{𝖬𝖮𝖣}}_p$ gates with unbounded fan-in. The class ${\mathrm{𝖠𝖢𝖢}}^0$ is defined as circuits of constant depth consisting of $\mathrm{𝖠𝖭𝖣},\mathrm{𝖮𝖱},\mathrm{𝖭𝖮𝖳}$ and ${\mathrm{𝖬𝖮𝖣}}_m$ gates of unbounded fan-in, for any fixed composite number $m$.
We define the following class of circuits, which can efficiently represent ${\mathrm{𝖠𝖢𝖢}}^0$ circuits [1, 2, 8].

We also use modulus amplifying polynomials in our algorithms for ${\mathrm{𝖠𝖢𝖢}}^0\circ 3\text{-}\mathrm{𝖯𝖳𝖥}$ satisfiability.

We review some facts on probabilistic matrices and probabilistic polynomials.

To derandomize algorithms that use probabilistic polynomials, we will need to design probabilistic polynomials that can be sampled using less randomness. To be precise, we say that a probabilistic polynomial $𝐏$ can be sampled in time $T(n)$ using $r(n)$ bits of randomness if there exists a deterministic algorithm $𝒜$ that takes as input a string $\sigma \in {\{0,1\}}^{r(n)}$ and in time $T(n)$ outputs polynomials, such that for each polynomial $P$, ${\mathrm{Pr}}_{\sigma \sim {\{0,1\}}^{r(n)}}[𝒜(\sigma )=P]=𝐏(P)$. We will also need to reduce the error of a probabilistic polynomial to any arbitrary $\epsilon >0$.

All our satisfiability algorithms rely on the fact that we can rapidly multiply rectangular matrices using Coppersmith’s algorithm.

We refer the reader to the appendix of [34] for a proof.

Letting $\mathrm{𝖬𝖠𝖩}$ be a function from ${\mathbb{Z}}_p^{\mathrm{\ell }}\to {\mathbb{Z}}_p$⁸⁸8We just let $\mathrm{𝖬𝖠𝖩}$ be the standard majority function on $z\in {\{0,1\}}^{\mathrm{\ell }}$, and arbitrarily set it to (say) $0$ on all other $z\in {𝔽}_p^{\mathrm{\ell }}$, we can define coefficients $k_a\in ℂ$ for each $a\in {𝔽}_p^{\mathrm{\ell }}$, such that $\mathrm{𝖬𝖠𝖩}(z_1,\mathrm{\dots },z_{\mathrm{\ell }})={\sum }_{a\in {𝔽}_p^{\mathrm{\ell }}}{k}_a\cdot \left({\sum }_{i=1}^{\mathrm{\ell }}{a}_i{z}_{i}modp\right)$. The quantity $\left({\sum }_{i=1}^{\mathrm{\ell }}{a}_i{z}_{i}modp\right)$ is interpreted as a real number. The numbers $k_a$ can be computed for each $a\subseteq {𝔽}_p^{\mathrm{\ell }}$ in time $2^{O(\mathrm{\ell })}$ using the FFT algorithm. We refer the reader to [23] for more details. Define the polynomials $P_a^{z,\sigma }:={\sum }_{i=1}^{\mathrm{\ell }}{a}_i{P}_i^{z,\sigma }$, and let $F_t$ denote the $t$-th Beigel-Tarui modulus amplifying polynomial (Definition 5).

Set $n^{\prime }=\frac{\sqrt{n}}{p(\log M,\log n){\log }^{d-1}s}$ for a suitable polynomial $p$. Let $m:=n-n^{\prime }$ We remind the reader that $\mathrm{\ell }=A{n}^{\prime }$ and that $r=B(\log M+{\log }^{2}n+\log s+\log (1/\epsilon ))=O(\log M+{\log }^{2}n+\log s+\log n^{\prime })$ for constants $A,B$. We choose $t=n^{\prime }/{\log }_2(p)+\mathrm{\ell }+r/{\log }_2(p)+10$. Now, we can present the deterministic algorithm.

1. 1.

   Calculate the coefficients $k_a$ for each $a\in {𝔽}_p^{\mathrm{\ell }}$ for $\mathrm{𝖬𝖠𝖩}$.

2. 2.

   For each $z\in {\{0,1\}}^{n^{\prime }},\sigma \in {\{0,1\}}^r,a\in {𝔽}_p^{\mathrm{\ell }}$, construct the polynomials $P_a^{z,\sigma }$ as sums of monomials and functions $f_i,g_i$, using Lemma 14.

3. 3.

   For each $i\in \{1,2,\mathrm{\dots },2^{n^{\prime }}\}$, construct as a sum of monomials, the polynomial

   $$R:=\sum _{z\in {\{0,1\}}^{n^{\prime }}}\sum _{\sigma \in {\{0,1\}}^r}\sum _{a\in {𝔽}_p^{\mathrm{\ell }}}{k}_a\cdot F_t\circ P_a^{z,\sigma }.$$

4. 4.

   For each $x,y\in {\{0,1\}}^{m/2}$, evaluate $R(f(x),g(y))$ using Coppersmith’s algorithm.

5. 5.

   Output ${\sum }_{(x,y)\in {\{0,1\}}^{m/2}\times {\{0,1\}}^{m/2}}\left[\left(R(f(x),g(y))mod{p}^t\right)/2^r\right]$ (where $[\cdot ]$ denotes the nearest integer function).

Step 1 takes time $2^{O(\mathrm{\ell })}=2^{O(n^{\prime })}$, which can be upper bounded (very loosely) by $2^{n/10}\cdot \mathrm{poly}(n,M,s)$. Step 2 takes time $2^{n^{\prime }+r+\mathrm{\ell }{\log }_{2}p}\cdot 2^{\sqrt{n}{\log }^{d-1}s\cdot \mathrm{polylog}(n,M)}$, which can be upper bounded by $2^{n/10}\cdot \mathrm{poly}(n,M,s)$ as well. To upper bound the complexity of Step 3, note that $R$ has $2^{n^{\prime }+r+\mathrm{\ell }{\log }_{2}p}\cdot 2^{t\sqrt{n}{\log }^{d-1}s\cdot \mathrm{poly}(\log n,\log M)}$ monomials. Choosing the polynomial $p$ appropriately, this can be upper bounded by $2^{0.01n}$. Hence, we can construct the polynomial for each $a,z,\sigma$ in time $\mathrm{poly}(n,M,s)\cdot 2^{n/10}$. Because the number of monomials in $R$ is upper bounded by $2^{0.05m}$, Step 4 takes $2^m\mathrm{poly}(m)$ time (Lemma 9). Step 5 runs in $2^m\mathrm{poly}(m)$ time as well.