Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

Satisfiability and Derandomization for Small Polynomial Threshold Circuits

Valentine Kabanets, Zhenjian Lu

Published Jan 1, 2018• 7 citations
Publisher

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 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).

DOI
10.4230/lipics.approx-random.2018.46

Related papers

A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush +2 more

We show that there is a zero-error randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time. Formally, for any constants d,k, there is an epsilon > 0 such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-d circuit C made up of k-PTF gates such that C has size at most n^{1+epsilon}. The algorithm runs in time 2^{n-n^{Omega(epsilon)}}. Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-k PTF (which is a depth-1 circuit of linear size). The main new tool is the use of a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into a memoization approach that yields the #SAT algorithms.

Leibniz international proceedings in informatics•Jan 1, 2019•2 citations

Efficient deterministic approximate counting for low-degree polynomial threshold functions

Anindya De, Rocco A. Servedio

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.

arXiv:1311.7178•ACM Symposium on Theory of Computing (STOC)•May 31, 2014•15 citations

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma

Rocco A. Servedio, Li-Yang Tan

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.

Leibniz international proceedings in informatics•Jan 1, 2021•0 citations

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

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.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•7 citations

Deterministic approximate counting of depth-2 circuits

Michael G. Luby, Boban Veličković, Avi Wigderson

The authors describe deterministic algorithms which for a given depth-2 circuit F approximate the probability that on a random input F outputs a specific value alpha . The approach gives an algorithm which for a given GF(2) multivariate polynomial p and given in >0 approximates the number of zeros (or ones) of p within a multiplicative factor 1+ in . The algorithm runs in time exp(exp(O( square root log(n/ in )))), where n is the size of the circuit. They also obtain an algorithm which given a DNF formula F and in >0 approximates the number of satisfying assignments of F within a factor of 1+ in and runs in time exp(O((log(n/ in ))/sup 4/)).>

Israel Symposium on Theory and Computing Systems (ISTCS)•Dec 30, 2002•82 citations

The Large-Error Approximate Degree of AC^0

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.

Leibniz international proceedings in informatics•Jan 1, 2019•3 citations
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).
We show that there is a zero-error randomized algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time. Formally, for any constants d,k, there is an epsilon > 0 such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-d circuit C made up of k-PTF gates such that C has size at most n^{1+epsilon}. The algorithm runs in time 2^{n-n^{Omega(epsilon)}}. Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-k PTF (which is a depth-1 circuit of linear size). The main new tool is the use of a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into a memoization approach that yields the #SAT algorithms.
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.
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.
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.
The authors describe deterministic algorithms which for a given depth-2 circuit F approximate the probability that on a random input F outputs a specific value alpha . The approach gives an algorithm which for a given GF(2) multivariate polynomial p and given in >0 approximates the number of zeros (or ones) of p within a multiplicative factor 1+ in . The algorithm runs in time exp(exp(O( square root log(n/ in )))), where n is the size of the circuit. They also obtain an algorithm which given a DNF formula F and in >0 approximates the number of satisfying assignments of F within a factor of 1+ in and runs in time exp(O((log(n/ in ))/sup 4/)).>
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.