Satisfiability and Derandomization for Small Polynomial Threshold Circuits

摘要

A polynomial threshold function (PTF) is defined as the sign of a polynomial p : ool n 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+ d wires, where d depends only on c and d , the number of satisfying assignments of the circuit can be computed in randomized time 2 n ? n 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- 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 ( log n ) O 2 and determines the majority value of C . (We obtain a similar quantified derandomization result for PTF circuits with n -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- PTFs with the seed length exp log n log 2 (1 ) .