A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.
Satisfiability (#SAT). We give the first zero-error randomized algorithm faster than exhaustive search that counts the number of satisfying assignments of a given constant-depth circuit with a super-linear number of wires whose gates are $s$-sparse PTFs, for $s$ almost quadratic in the input size of the circuit; here a PTF is called $s$-sparse if its underlying polynomial has at most $s$ monomials. More specifically, we show that, for any large enough constant $c$, given a depth-$d$ circuit with $(n^{2-1/c})$-sparse PTF gates that has at most $n^{1+\varepsilon_d}$ wires, where $\varepsilon_d$ depends only on $c$ and $d$, the number of satisfying assignments of the circuit can be computed in randomized time $2^{n-n^{\varepsilon_d}}$ with zero error. This generalizes the result by Chen, Santhanam and Srinivasan (CCC, 2016) who gave a SAT algorithm for constant-depth circuits of super-linear wire complexity with linear threshold function (LTF) gates only.
Quantified derandomization. The quantified derandomization problem, introduced by Goldreich and Wigderson (STOC, 2014), asks to compute the majority value of a given Boolean circuit, under the promise that the minority-value inputs to the circuit are very few. We give a quantified derandomization algorithm for constant-depth PTF circuits with a super-linear number of wires that runs in quasi-polynomial time. More specifically, we show that for any sufficiently large constant $c$, there is an algorithm that, given a degree-$\Delta$ PTF circuit $C$ of depth $d$ with $n^{1+1/c^d}$ wires such that $C$ has at most $2^{n^{1-1/c}}$ minority-value inputs, runs in quasi-polynomial time $\exp\left((\log n)^{O\left(\Delta^2\right)}\right)$ and determines the majority value of $C$. (We obtain a similar quantified derandomization result for PTF circuits with $n^{\Delta}$-sparse PTF gates.) This extends the recent result of Tell (STOC, 2018) for constant-depth LTF circuits of super-linear wire complexity.
Pseudorandom generators. We show how the classical Nisan-Wigderson (NW) generator (JCSS, 1994) yields a nontrivial pseudorandom generator for PTF circuits (of unrestricted depth) with sub-linearly many gates. As a corollary, we get a PRG for degree-$\Delta$ PTFs with the seed length $\exp\left(\sqrt{\Delta\cdot\log n}\right)\cdot\log^2(1/\epsilon)$.
