Abstract
A polynomial threshold function (PTF) is defined as the sign of a polynomial p : {0,1}^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 zeroerror randomized algorithm faster than exhaustive search that counts the number of satisfying assignments of a given constantdepth circuit with a superlinear number of wires whose gates are ssparse PTFs, for s almost quadratic in the input size of the circuit; here a PTF is called ssparse if its underlying polynomial has at most s monomials. More specifically, we show that, for any large enough constant c, given a depthd circuit with (n^{21/c})sparse PTF gates that has at most n^{1+epsilon_d} wires, where epsilon_d depends only on c and d, the number of satisfying assignments of the circuit can be computed in randomized time 2^{nn^{epsilon_d}} with zero error. This generalizes the result by Chen, Santhanam and Srinivasan (CCC, 2016) who gave a SAT algorithm for constantdepth circuits of superlinear 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 minorityvalue inputs to the circuit are very few. We give a quantified derandomization algorithm for constantdepth PTF circuits with a superlinear number of wires that runs in quasipolynomial time. More specifically, we show that for any sufficiently large constant c, there is an algorithm that, given a degreeDelta PTF circuit C of depth d with n^{1+1/c^d} wires such that C has at most 2^{n^{11/c}} minorityvalue inputs, runs in quasipolynomial time exp ((log n)^{O (Delta^2)}) 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 constantdepth LTF circuits of superlinear wire complexity.
 Pseudorandom generators. We show how the classical NisanWigderson (NW) generator (JCSS, 1994) yields a nontrivial pseudorandom generator for PTF circuits (of unrestricted depth) with sublinearly many gates. As a corollary, we get a PRG for degreeDelta PTFs with the seed length exp (sqrt{Delta * log n})* log^2(1/epsilon).
BibTeX  Entry
@InProceedings{kabanets_et_al:LIPIcs:2018:9450,
author = {Valentine Kabanets and Zhenjian Lu},
title = {{Satisfiability and Derandomization for Small Polynomial Threshold Circuits}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {46:146:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9450},
URN = {urn:nbn:de:0030drops94507},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.46},
annote = {Keywords: constantdepth circuits, polynomial threshold functions, circuit analysis algorithms, SAT, derandomization, quantified derandomization, pseudorandom g}
}
Keywords: 

constantdepth circuits, polynomial threshold functions, circuit analysis algorithms, SAT, derandomization, quantified derandomization, pseudorandom g 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 