We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}^n. This result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d \geq 1, \eps \geq 0, every degree-d PTF over n variables has can be approximated to accuracy eps by a constant-degree PTF that has integer weights of total magnitude O(n^d). This weight bound is shown to be optimal up to constant factors.
We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {-1,1}^n. This result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d \geq 1, \eps \geq 0, every degree-d PTF over n variables has can be approximated to accuracy eps by a constant-degree PTF that has integer weights of total magnitude O(n^d). This weight bound is shown to be optimal up to constant factors.
We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman’s regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Rocco A. Servedio and Li-Yang Tan, 2018] pseudorandom generator for PTFs.
The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is independent of the dimension. That is, we show that Boolean degree-d PTFs are robustly identifiable from their degree-d Chow parameters. No non-trivial bound was previously known for d >1.
We give a deterministic algorithm for approximately counting satisfying assignments of a degree-d polynomial threshold function (PTF). Given a degree-d input polynomial p(x) over Rn and a parameter ε > 0, our algorithm approximates Pr [EQUATION] to within an additive ±ε in time Od,ε(1) · poly(nd). (Since it is NP-hard to determine whether the above probability is nonzero, any sort of efficient multiplicative approximation is almost certainly impossible even for randomized algorithms.) Note that the running time of our algorithm (as a function of nd, the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem [Kan12b], based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time [EQUATION] for all c > 0.
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 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+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^{n-n^{epsilon_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 ((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 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 (sqrt{Delta * log n})* log^2(1/epsilon).
Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.
Let g:{−1,1}k→{−1,1} be any Boolean function and q1,…,qk be any degree-2 polynomials over {−1,1}n. We give a \emph{deterministic} algorithm which, given as input explicit descriptions of g,q1,…,qk and an accuracy parameter $\eps>0$, approximates \[\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1]\] to within an additive $\pm \eps$. For any constant $\eps > 0$ and k≥1 the running time of our algorithm is a fixed polynomial in n. This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result \cite{DDS13:deg2count} which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function $\sign(q(x)),$ corresponding to the k=1 case of our result. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k=1 case in \cite{DDS13:deg2count}. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution. Finally, a third new ingredient is a "regularity lemma" for \emph{k-tuples} of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of \cite{DSTW:10,HKM:09} and the regularity lemma of Gopalan et al \cite{GOWZ10}. Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.