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:1503.07261

Dual Polynomials for Collision and Element Distinctness

Mark Bun, Justin Thaler

Published Mar 25, 2015• 6 citations
arXivHTMLPDF

Abstract

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tildeΩ(n^{1/3})$ and $\tildeΩ(n^{2/3})$ lower bounds on the approximate degree of the Collision and Element Distinctness functions, respectively. Their proof was non-constructive, using a sophisticated symmetrization argument and tools from approximation theory. More recently, several open problems in the study of approximate degree have been resolved via the construction of dual polynomials. These are explicit dual solutions to an appropriate linear program that captures the approximate degree of any function. We reprove Aaronson and Shi's results by constructing explicit dual polynomials for the Collision and Element Distinctness functions.

DOI
10.48550/arxiv.1503.07261

Related papers

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

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.

Foundations and Trends® in Theoretical Computer Science•Dec 30, 2022•11 citations

Improved Approximate Degree Bounds For k-distinctness

Nikhil S. Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

arXiv:2002.08389•Leibniz international proceedings in informatics•Jan 1, 2020•15 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 polynomial method strikes back: tight quantum query bounds via dual polynomials

Mark Bun, Robin Kothari, Justin Thaler

The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001).

arXiv:1710.09079•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•58 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = \Omega(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-\Omega(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $\delta > 0$ we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves upon the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant $\delta > 0$, an $\Omega(n^{1-\delta})$ lower bound on the quantum communication complexity of a function in AC$^0$; (ii) a Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$; this separation is optimal up to the $o(1)$ term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC$^0$.

arXiv:1703.05784•SIAM Journal on Computing•Oct 22, 2019•18 citations
The approximate degree of a Boolean function f:{−1,1}n→{−1,1}f: \{-1, 1\}^n \to \{-1, 1\}f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates fff to within error 1/31/31/3 in the ℓ∞\ell_\inftyℓ∞​ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight Ω~(n1/3)\tildeΩ(n^{1/3})Ω~(n1/3) and Ω~(n2/3)\tildeΩ(n^{2/3})Ω~(n2/3) lower bounds on the approximate degree of the Collision and Element Distinctness functions, respectively. Their proof was non-constructive, using a sophisticated symmetrization argument and tools from approximation theory. More recently, several open problems in the study of approximate degree have been resolved via the construction of dual polynomials. These are explicit dual solutions to an appropriate linear program that captures the approximate degree of any function. We reprove Aaronson and Shi's results by constructing explicit dual polynomials for the Collision and Element Distinctness functions.
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 degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.
An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).
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.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0^00
The approximate degree of a Boolean function f ⁣:{−1,1}n→{−1,1}f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates fff pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function fff with approximate degree ddd into a function FFF on O(n⋅polylog(n))O(n \cdot \mathrm{polylog}(n))O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3)D = \Omega(n^{1/3} \cdot d^{2/3})D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1)d= n^{1-\Omega(1)}d=n1−Ω(1), then DDD is polynomially larger than ddd. Moreover, if fff is computed by a polynomial-size Boolean circuit of constant depth, then so is FFF. By recursively applying our transformation, for any constant δ>0\delta > 0δ>0 we exhibit an AC0^00 function of approximate degree Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of nnn that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant δ>0\delta > 0δ>0, an Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0^00; (ii) a Boolean function fff with approximate degree at least C(f)2−o(1)C(f)^{2-o(1)}C(f)2−o(1), where C(f)C(f)C(f) is the certificate complexity of fff; this separation is optimal up to the o(1)o(1)o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC0^00.