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

arXiv:1811.03491 · ACM Symposium on Theory of Computing (STOC)

Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)

Ilias Diakonikolas, Daniel M. Kane

Published Jun 20, 2019• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/3313276.3316301

Related papers

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Anindya De, Ilias Diakonikolas, Vitaly Feldman +1 more

The Chow parameters of a Boolean function f: {-1,1}n -> {-1,1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time ~O(n2)• (1/ε)O(log2(1/ε)) and with high probability outputs a representation of an LTF f' that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) • 22~O(1/ε2).

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•12 citations

Degree and Sensitivity: tails of two distributions

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal +1 more

The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.

arXiv:1604.07432•Electronic colloquium on computational complexity•Apr 25, 2016•15 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

Approximating the AND-OR Tree.

Alexander A. Sherstov

ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function

Electronic colloquium on computational complexity•Jan 1, 2013•5 citations

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: $O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the $k$-element distinctness problem; $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; and $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

arXiv:1801.04607•SIAM Journal on Computing•Jan 1, 2020•10 citations

On the Approximate Non-Deterministic Degree of Total Boolean Functions

Samruddhi Pednekar, Supartha Podder

The approximate non-deterministic degree of a Boolean function $f$, denoted $\mathsf{ndeg}_ε(f)$ (written $\mathsf{N}_ε(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \le |p(x)| \le ε$ whenever $f(x) = 0$, and $|p(x)| \ge 1$ whenever $f(x) = 1$. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on $1$-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all $0$-inputs and bounded away from zero on all $1$-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function $f$, \[ deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). \] In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by $\mathsf{N}_ε(f)$ and $\mathsf{N}_ε(\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<ε<1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). \] This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, $k$-uniform hypergraph properties, and read-$k$ Disjunctive Normal Form (DNF) formulas.

cs.CCCross-listedarXiv:2605.23336•May 25, 2026•0 citations
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.
The Chow parameters of a Boolean function f: {-1,1}n -> {-1,1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time ~O(n2)• (1/ε)O(log2(1/ε)) and with high probability outputs a representation of an LTF f' that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) • 22~O(1/ε2).
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.
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.
The approximate degree of a Boolean function f(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: O(n34−14(2k−1))O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; and O(n3/4)O(n^{3/4})O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n)\Theta(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)\Omega(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
The approximate non-deterministic degree of a Boolean function fff, denoted ndegε(f)\mathsf{ndeg}_ε(f)ndegε​(f) (written Nε(f)\mathsf{N}_ε(f)Nε​(f) for brevity), is the minimum degree of a real polynomial ppp such that 0≤∣p(x)∣≤ε0 \le |p(x)| \le ε0≤∣p(x)∣≤ε whenever f(x)=0f(x) = 0f(x)=0, and ∣p(x)∣≥1|p(x)| \ge 1∣p(x)∣≥1 whenever f(x)=1f(x) = 1f(x)=1. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on 111-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all 000-inputs and bounded away from zero on all 111-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function fff, deg(f)≤O~ ⁣(rdeg⁡(f)3). deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). deg(f)≤O(rdeg(f)3). In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by Nε(f)\mathsf{N}_ε(f)Nε​(f) and Nε(f‾)\mathsf{N}_ε(\overline{f})Nε​(f​) jointly, i.e., for every total Boolean function fff and every constant 0<ε<10<ε<10<ε<1, deg~(f)≤poly⁡(Nε(f),Nε(f‾)). \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). deg​(f)≤poly(Nε​(f),Nε​(f​)). This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, kkk-uniform hypergraph properties, and read-kkk Disjunctive Normal Form (DNF) formulas.