Authors Mark Bun, Justin Thaler,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34
www.theoryofcomputing.org
Dual Polynomials for
Collision and Element Distinctness
Mark Bun∗ Justin Thaler†
Received August 17, 2015; Revised May 8, 2016; Published October 13, 2016
Abstract: The approximate degree of a Boolean function f : {−1, 1}n → {−1, 1} is the
minimum degree of a real polynomial that approximates f to within error 1/3 in the `∞
norm. In an influential result, Aaronson and Shi (J. ACM, 2004) proved tight Ω(ne 1/3 ) and
Ω(n
e 2/3 ) lower bounds on the approximate degree of the C OLLISION and E LEMENT D IS -
TINCTNESS 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 C OLLISION
and E LEMENT D ISTINCTNESS functions. Our constructions are heavily inspired by Kutin’s
(Theory of Computing, 2005) refinement and simplification of Aaronson and Shi’s results.
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q12, 68Q17
Key words and phrases: polynomials, polynomial approximation, approximate degree, quantum com-
puting, collision problem, element distinctness
∗ Harvard University, School of Engineering and Applied Sciences. Supported by an NDSEG Fellowship and NSF grant
CNS-1237235.
† Yahoo Research. Parts of this work were performed while the author was a Research Fellow at the Simons Institute for the
Theory of Computing. Supported in part by a Research Fellowship from the Simons Institute for the Theory of Computing.
© 2016 Mark Bun and Justin Thaler
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2016.v012a016
M ARK B UN AND J USTIN T HALER
1 Introduction
The ε-approximate degree of a Boolean function f : {−1, 1}n → {−1, 1} is the least degree of a real
polynomial that approximates f to within error ε in the `∞ norm. Approximate degree is a fundamental
measure of the complexity of a Boolean function, and has wide-ranging applications in theoretical
computer science. For example, approximate degree upper bounds underlie several of the best known
algorithms for PAC learning [26], agnostic learning [24, 25], learning in the presence of irrelevant
information [27, 35], and differentially private data release [49, 21]. Meanwhile, lower bounds on
approximate degree imply many optimal lower bounds on quantum query complexity, circuit complexity,
and communication complexity (see for example [11, 37, 5, 18, 45, 38, 13, 12, 36]).
In an influential result, Aaronson and Shi proved tight Ω(ne 1/3 ) and Ω(n
e 2/3 ) lower bounds on the
approximate degree of the C OLLISION and E LEMENT D ISTINCTNESS functions [5].1 The C OLLISION
lower bound matched an earlier O(n1/3 ) upper bound due to Brassard et al. [17], while the lower bound
for E LEMENT D ISTINCTNESS was later shown to be tight by Ambainis [9].
The C OLLISION lower bound subsequently found many applications and extensions in quantum
complexity theory; Aaronson recently provided a retrospective overview of these developments [4].
e 2/3 ) lower bound for E LEMENT D ISTINCTNESS remains the best known approximate
Moreover, the Ω(n
degree lower bound for any function in AC0 .
Aaronson and Shi proved their lower bound for C OLLISION with a symmetrization argument. This
style of argument proceeds in two steps. First, a polynomial p on n variables (which is assumed to
approximate the target function f ) is transformed into a polynomial q on m < n variables in such a
way that deg(q) ≤ deg(p). Second, a lower bound on deg(q) is proved, typically by applying Markov-
Bernstein type inequalities from approximation theory. Aaronson and Shi’s proof of the C OLLISION
lower bound is a particularly sophisticated application of this style of argument.
The lower bound for E LEMENT D ISTINCTNESS follows from a reduction to the lower bound for
C OLLISION. This reduction is discussed in Section 5.
1.1 The method of dual polynomials
Despite the many applications of approximate degree in theoretical computer science, significant gaps
remain in our understanding of this complexity measure, and there are many simple functions whose
approximate degree remains unknown. The slow nature of progress can be attributed in part to the
limitations of symmetrization arguments. At an intuitive level, the process of symmetrization is inherently
lossy: by turning a polynomial p on n variables into a polynomial q on m < n variables, information
about p is necessarily thrown away. Hence, several works have identified that an important research
direction is to develop techniques beyond symmetrization for lower bounding the approximate degree of
Boolean functions [2, 41, 19].
The last few years have seen significant progress toward this goal. In particular, a series of works
has proved new approximate degree lower bounds for important classes of functions by constructing
1 Aaronson established a lower bound of Ω(n
e 1/5 ) for the C OLLISION function in a paper that appeared in STOC 2002 [1],
e 1/3 ) in a FOCS paper that same year [44]. A joint journal paper appeared in 2004 [5]. The
and Shi improved it to the tight Ω(n
proof was simplified and extended to the “small range” case by Kutin [28]. Ambainis [7] independently extended Aaronson and
Shi’s lower bound to the small range case, using different techniques than Kutin.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 2
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
explicit dual polynomials, which are dual solutions to a certain linear program capturing the approximate
degree of any function. These polynomials act as certificates of the high approximate degree of a function.
Moreover, strong LP duality implies that the technique is lossless, in contrast to symmetrization. That is,
for any function f and any ε, there is always some dual polynomial φ that witnesses a tight approximate
degree lower bound for f ; the challenge is to construct φ .
This “method of dual polynomials” was recently used to resolve the approximate degree of the
AND-OR tree [40, 19], closing a long line of incrementally larger lower bounds [44, 7, 23, 41, 30]. It has
also been used to establish several “hardness amplification” results for approximate degree [48, 20, 42],
and to prove new threshold degree lower bounds for several important classes of functions, including
the intersection of two majorities [31, 41] and AC0 [42, 43]. The latter result represented the first
superlogarithmic improvement over Minsky and Papert’s seminal Ω(n1/3 ) lower bound from 1969 on the
threshold degree of an AC0 function. We also note that dual polynomials have been used via the pattern
matrix method [38] to resolve several longstanding open problems in communication complexity (see the
survey of Sherstov [36]). The pattern matrix method uses dual polynomials to construct distributions
under which various communication problems are hard (see the next section for more details).
1.2 Contribution and motivation
We reprove Aaronson and Shi’s results by constructing explicit dual polynomials for the C OLLISION
and E LEMENT D ISTINCTNESS functions.2 First, we give a direct construction of a dual polynomial
for C OLLISION. The construction of this dual polynomial is heavily inspired by Kutin’s refined proof
of the C OLLISION lower bound [28]. In Section 2.5, we give an overview of the ideas that go into
this construction. In Section 5, we give a generic reduction which shows show how to turn any dual
polynomial ψ for C OLLISION into a dual polynomial ϕ for E LEMENT D ISTINCTNESS. We construct
ϕ(x) by averaging ψ(y) over a carefully constructed set of extensions from each x to a longer input y.
We have four main motivations for reproving Aaronson and Shi’s lower bound in this manner.
1. First, only a handful of techniques are currently known for the construction of dual polynomials,
especially for the case where ε = Θ(1). To date, dual polynomials have been constructed only for
symmetric functions [46, 19] and a handful of highly structured block-composed functions [20,
19, 40, 41, 42, 43, 39]. (A block-composed function F : {−1, 1}M·N → {−1, 1} is a function of the
form of the form F = g( f (x1 ), . . . , f (xM )) for some g : {−1, 1}M → {−1, 1} and f : {−1, 1}N →
{−1, 1}.) The C OLLISION and E LEMENT D ISTINCTNESS functions fall into neither category; our
constructions of dual polynomials for these problems introduce several new techniques that we are
optimistic will prove useful in future applications.
In particular, we hope that our techniques will prove useful for establishing new, stronger ap-
proximate degree lower bounds for AC0 . Up to polylogarithmic factors, the best lower bound
on the approximate degree of any function in AC0 is the Ω(n
e 2/3 ) lower bound for the E LEMENT
D ISTINCTNESS function. Meanwhile, no o(n) upper bound is known. Resolving the approximate
degree of AC0 remains a significant open problem with many complexity-theoretic applications,
and the new techniques that we use to construct dual polynomials may help close the gap.
2 Like Kutin’s simplification and refinement of Aaronson and Shi’s original proof of the C OLLISION lower bound, our
construction yields a dual polynomial for the C OLLISION function even in the “small-range” case.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 3
M ARK B UN AND J USTIN T HALER
2. A second motivation is to shed new light on the C OLLISION lower bound itself. The earlier
symmetrization-based proof [5, 28], while shorter than ours, is non-constructive and relies on
Markov-Bernstein inequalities from approximation theory. In contrast, our proof is constructive
and entirely elementary. We also believe that our analysis illuminates some of the more miraculous
aspects of the earlier symmetrization-based proof—see Section 2.6 for further discussion of this
point.
3. Our third motivation is to make explicit the proofs of several of the best known bounds in the
complexity-theoretic study of constant-depth circuits. In particular, very recent work of Sher-
stov [43] exhibits a function F in AC0 with threshold degree Ω(n1/2 ). The function F is obtained
by block-composing the E LEMENT D ISTINCTNESS function with a certain constant-depth Boolean
formula, and Sherstov’s proof is via the method of dual polynomials. There is only one non-explicit
element in Sherstov’s construction of a dual polynomial φ witnessing the fact that the threshold
degree of F is in Ω(n1/2 ); he uses, in a black-box manner, the existence of a dual polynomial for
E LEMENT D ISTINCTNESS. In giving the first explicit construction of such a dual polynomial, we
render Sherstov’s construction of φ fully explicit. This has the following implication.
By applying the pattern matrix method to Sherstov’s function F, one obtains a function G in
AC0 with discrepancy exp(−Ω(n1/2 )).3 This is the strongest known bound on the discrepancy
of a function in AC0 , improving over a lengthy line of work (see Table 1). However, because
the construction of the dual polynomial φ in [43] is not entirely explicit, combining Sherstov’s
result [43] with the pattern matrix method does not give an explicit distribution under which G has
low discrepancy. Our construction of a dual polynomial for E LEMENT D ISTINCTNESS remedies
this situation, yielding the first explicit distribution under which an AC0 function has discrepancy
exp(−Ω(n1/2 )).
We remark that several other applications of the method of dual polynomials have utilized the
existence of a dual polynomial for E LEMENT D ISTINCTNESS in a black-box fashion [42, 20]. Our
results render explicit these dual polynomial constructions as well.
4. Finally, following the initial dissemination of this work, Bogdanov et al. [16] used our dual
polynomial for E LEMENT D ISTINCTNESS to design an explicit secret sharing scheme with a
reconstruction algorithm computable by an AC0 circuit. An (n, d)-secret sharing scheme with
reconstruction advantage ε is a procedure that enables a dealer to share a secret bit between
n parties in such a way that any coalition of at most d parties learns nothing about the secret,
but the n parties can combine all of their shares to recover a (randomly chosen) secret with
probability at least 1/2 + ε. Bogdanov et al. [16] showed that if the ε-approximate degree of
a function f : {−1, 1}n → {−1, 1} is at least d, then there exists a (n, d)-secret sharing scheme
with reconstruction advantage at least ε/2, in which the n parties apply f to their shares in order
to reconstruct the secret bit. Moreover, the distributions from which the dealer samples shares
are exactly determined by a dual polynomial for f . Thus, for any constant ε < 1, our dual
3 Low discrepancy implies high communication cost in nearly every communication model. We refer the reader to [38,
Section 10] and [42, Section 8] for the definition of discrepancy and applications of discrepancy upper bounds to communication
complexity, computational learning theory, and circuit complexity.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 4
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Discrepancy Reference Explicit Distribution Given?
exp(−Ω(n1/3 )) [18] No
exp(−Ω(n1/3 )) [38] Yes
exp(−Ω(n2/5 )) [20] No
exp(−Ω(n1/2−δ )) for any constant δ > 0 [42] Yes
exp(−Ω(n1/2 )) [43] No
exp(−Ω(n1/2 )) This work Yes
Table 1: Upper bounds on the discrepancy of circuits of constant depth and polynomial size.
polynomial for E LEMENT D ISTINCTNESS yields an explicit (n, Ω(n e 2/3 ))-secret sharing scheme
with reconstruction advantage at least ε/2. Bogdanov et al. additionally showed that the structure
of our dual polynomial enables these shares to be sampled by AC0 circuits.
1.3 Related work on quantum query complexity
Aaronson and Shi’s original motivation for studying the approximate degree of the C OLLISION function
was to understand its quantum query complexity. (Recall that approximate degree provides a lower
bound on quantum query complexity [11]. However, it is known that the lower bound is not always
tight [8].) Subsequent to Aaronson and Shi’s work, a body of lower bound techniques collectively known
as adversary methods were developed for quantum query complexity [22, 6, 47, 8, 52, 10]. It is now
known that one of the most general forms of the adversary method, called the negative-weights adversary
method [22], always gives a tight characterization of quantum query complexity [33, 34]. (Moreover, the
polynomial method can be viewed as a special case of the multiplicative adversary method [29].)
The negative-weights adversary method for lower bounding quantum query complexity is closely
analogous to the method of dual polynomials for approximate degree; the former is characterized by a
semidefinite program, and a solution to this semidefinite program is known as an adversary matrix. A
recent line of work, similar in spirit to our own, has proved or reproved optimal quantum query complexity
lower bounds for several functions by constructing explicit adversary matrices. In particular, Belovs and
Rosmanis [14] constructed an optimal adversary matrix for the C OLLISION function in the “large range”
case (note that the dual polynomial that we construct applies even in the “small range” case), and Belovs
and Špalek constructed an optimal adversary matrix for the E LEMENT D ISTINCTNESS function [15].
Very recently, Zhandry [51] (improving on work of Yuen [50]) proved a tight lower bound of Ω(N 1/3 )
on the quantum query complexity of finding a collision in a randomly chosen function.
2 Preliminaries
2.1 Notation
For any positive integer n, we denote the set {1, . . . , n} by [n], and the set {0, 1, . . . , n} by [[n]]. For a
function f : D → R, define the L1 norm k f k1 = ∑x∈D | f (x)|. For any subset S ⊆ [n], we let χS : {−1, 1}n →
{−1, 1} denote the parity function on S, i. e., χS (x) = ∏i∈S xi .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 5
M ARK B UN AND J USTIN T HALER
2.2 Approximate degree and its dual characterization
Let D ⊆ {−1, 1}n , and let f : D → {−1, 1} be a partial Boolean function defined on D. A real polynomial
p : {−1, 1}n → R is said to ε-approximate f if
1. |p(x) − f (x)| ≤ ε for all x ∈ D, and
2. |p(x)| ≤ 1 + ε for all x ∈ {−1, 1}n .
The ε-approximate degree of f , denoted deg f ( f ), is the minimum degree of an ε-approximation for
ε
f f ) to denote deg
f . We use deg( f ( f ), and refer to this quantity without qualification as the approximate
1/3
f f ) is related to deg
degree of f . The choice of 1/3 is arbitrary, as deg( f ( f ) by a constant multiplicative
ε
factor for any constant ε ∈ (0, 1).
Given a partial Boolean function f , let p be a real polynomial that attains the smallest ε subject to the
constraints above, over all polynomials of degree at most d. Since we work over x ∈ {−1, 1}n , we may
assume without loss of generality that p is multilinear with the representation
p(x) = ∑ cS χS (x) ,
|S|≤d
where the coefficients cS are real numbers. Then p is an optimum of the following linear program.
min ε
such that f (x) − ∑|S|≤d cS χS (x) ≤ ε for each x ∈ D
∑|S|≤d cS χS (x) ≤ 1 + ε for each x ∈ {−1, 1}n \ D
cS ∈ R for each |S| ≤ d
ε ≥0
The dual linear program is as follows.
max ∑x∈D φ (x) f (x) − ∑x∈{−1,1}n \D |φ (x)|
such that ∑x∈{−1,1}n |φ (x)| = 1
∑x∈{−1,1}n φ (x)χS (x) = 0 for each |S| ≤ d
φ (x) ∈ R for each x ∈ {−1, 1}n
Strong LP-duality thus implies the following dual characterization of approximate degree.
Theorem 2.1. Let f : D → {−1, 1} be a partial Boolean function. Then deg
f ( f ) > d if and only if there
ε
n
is a polynomial φ : {−1, 1} → R such that
∑ f (x)φ (x) − ∑ |φ (x)| > ε · ∑ |φ (x)| , (2.1)
x∈D x∈{−1,1}n \D x∈{−1,1}n
and
∑ φ (x)χS (x) = 0 for each |S| ≤ d . (2.2)
x∈{−1,1}n
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 6
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
If φ satisfies (2.1), we say that φ has correlation greater than ε with f . If φ satisfies (2.2), i. e., all
Fourier coefficients of φ below degree d are zero, we say φ has pure high degree d. We refer to any
feasible solution φ to the dual linear program as an (ε, d)-dual polynomial for f .
2.3 The C OLLISION and E LEMENT D ISTINCTNESS functions
Let [N] = {1, . . . , N}, and fix a triple of positive integers n, N, R such that R ≥ N, and n = N · log2 R. For
simplicity throughout, we assume that R is a power of 2. The C OLLISION and E LEMENT D ISTINCTNESS
functions are typically thought of as properties of functions mapping [N] to [R]. However, it will be
convenient for us to think of them instead as functions on the Boolean hypercube {−1, 1}n . To this end,
given an input x ∈ {−1, 1}n , we interpret x as the evaluations of a function gx mapping [N] → [R]. That is,
we break x up into N blocks, each of length log2 R, and regard each block xi as the binary representation
of gx (i).
Definition 2.2 (C OLLISION Function). A function gx : [N] → [R] is said to be k-to-1 if for every i ∈ [N],
there exist exactly k − 1 values j 6= i such that gx (i) = gx ( j). Let Tk := {x ∈ {−1, 1}n : gx is k-to-1}
(clearly, Tk is non-empty only if k | N). The C OLLISION function, which we denote by ColN,R , is the
partial Boolean function defined on T1 ∪ T2 ⊆ {−1, 1}n such that ColN,R (x) = 1 if and only if x ∈ T1 . That
is, ColN,R is the partial Boolean function corresponding to the property that gx is a 1-to-1 function, with
the promise that gx is either 1-to-1 or 2-to-1.
Definition 2.3 (E LEMENT D ISTINCTNESS Function). The E LEMENT D ISTINCTNESS function, denoted
EDN,R , is the total Boolean function defined such that EDN,R (x) = 1 if and only if gx is 1-to-1. That is,
EDN,R is the total Boolean function corresponding to the property that gx is 1-to-1.
Let B ⊂ {−1, 1}n denote the set of inputs x such that gx is neither 1-to-1 nor 2-to-1. Then an
(ε, d)-dual polynomial φ for ColN,R has the following properties (cf. Section 2.2):
1. ∑x∈T1 φ (x) − ∑x∈T2 φ (x) − ∑x∈B |φ (x)| > ε · ∑x∈{−1,1}n |φ (x)|.
2. ∑x∈{−1,1}n φ (x)χS (x) = 0 for all |S| ≤ d.
Similarly, an (ε, d)-dual polynomial for EDN,R satisfies the following conditions.
1. ∑x∈T1 φ (x) − ∑x∈T
/ 1 φ (x) > ε · ∑x∈{−1,1}n |φ (x)|.
2. ∑x∈{−1,1}n φ (x)χS (x) = 0 for all |S| ≤ d.
2.4 Overview of the symmetrization-based proof of the C OLLISION lower bound
Kutin’s simplified proof of the C OLLISION lower bound [28] proceeds in two steps. The first step is a
symmetrization step, which establishes the following remarkable result. (We state this result slightly
informally in this overview.)
Lemma 2.4 (Informal version of Lemma 2.5). Call a triple (m, a, b) valid if a | m and b | (N − m). For
any triple (m, a, b), let Rm,a,b denote the set of inputs x ∈ {−1, 1}n such that gx : [N] → [R] maps m of its
inputs to [R] in an a-to-1 manner, and maps the remaining N − m of its inputs to [R] in a b-to-1 manner.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 7
M ARK B UN AND J USTIN T HALER
Let p(x) be a real polynomial over {−1, 1}n of degree d. Then there is a trivariate polynomial P of
total degree at most d such that for every valid triple (m, a, b), it holds that
P(m, a, b) = Ex∈Rm,a,b [p(x)] .
Note in the above lemma that the sets Rm,a,b are not uniquely determined; for instance Rm,1,1 =
R0,a,1 = RN,1,b = T1 for every triple (m, a, b).
The second step of Kutin’s proof argues that if p is a (1/3)-approximating polynomial for the
C OLLISION function, then P must have degree Ω(N 1/3 ). Hence by Lemma 2.4, p must have degree
Ω(N 1/3 ) as well.
In more detail, the second step of Kutin’s proof proceeds via a case analysis. Four cases are considered.
Case 1: P(N/2, 1, 2) ≥ 1/2, and |P(N/2, 1, b)| ≤ 2 for all b ∈ [N 2/3 ]. In this case, Kutin is able to apply
Markov’s inequality from approximation theory to conclude that the degree of P in its third variable
is Ω(N 1/3 ).
Case 2: P(N/2, 1, 2) ≥ 1/2, and |P(N/2, 1, b)| > 2 for some b ∈ [N 2/3 ]. In this case, Kutin is able to
apply Bernstein’s inequality from approximation theory to conclude that the degree of P in its first
variable is Ω(N 1/3 ).
Case 3: P(N/2, 1, 2) < 1/2, and |P(N/2, a, 2)| ≤ 2 for all a ∈ [N 2/3 ]. In this case, Kutin is able to apply
Markov’s inequality to conclude that the degree of P in its second variable is Ω(N 1/3 ).
Case 4: P(N/2, 1, 2) < 1/2, and |P(N/2, a, 2)| > 2 for some a ∈ [N 2/3 ]. In this case, Kutin is able to
apply Bernstein’s inequality to conclude that the degree of P in its first variable is Ω(N 1/3 ).
A key technical complication that must be dealt with in the argument above is that |P(m, a, b)| may be
much larger than 1 for invalid triples (m, a, b). This may seem like a minor technicality, but in fact it is a
central issue: if P(m, a, b) were bounded for all invalid triples, then it would be possible to argue that the
total degree of P is Ω(N 1/2 ), which would imply a (false) lower bound of Ω(N 1/2 ) on the approximate
degree of ColN,R .
2.5 Overview of our construction for the C OLLISION function
As with Kutin’s proof, our construction also makes essential use of Lemma 2.4. Whereas Kutin used
Lemma 2.4 to reduce to a setting where Markov-Bernstein inequalities could be applied in a non-
constructive manner, we instead use Lemma 2.4 to argue that the dual polynomial φ that we construct has
pure high degree Ω(N 1/3 ).
In more detail, we present our construction in two stages, in order to highlight distinct ideas that go
into the proof.pIn the first stage, we construct a simpler dual polynomial φ : {−1, 1}n → {−1, 1} that
exhibits an Ω( log N/ log log N) lower bound on the approximate degree of ColN,R . The second stage
constructs a dual polynomial ψ exhibiting the optimal Ω(N 1/3 ) lower bound.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 8
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Overview of the first stage. Let Hk ⊆ {−1, 1}n denote the set of inputs of Hamming weight k. The
symmetrization-based proof of the C OLLISION lower bound from [5, 28] carries the strong intuition that
the sets Tk should play the same role that Hk plays in Nisan and Szegedy’s seminal symmetrization-based
lower bound for the OR function [30]. We direct the interested reader to Aaronson’s lecture notes [3] for
a detailed explanation of this intuition. The construction of our simpler dual witness φ instantiates this
intuition in the dual setting.
Recall that a dual polynomial φ witnessing the fact that deg(Col N,R ) ≥ d must satisfy two properties:
f
(1) it must have correlation greater than ε with ColN,R , and (2) it must have pure high degree at least d. We
define φ in a way that mimics the structure of known dual witnesses for symmetric functions, even though
φ is not itself symmetric. Specifically, our construction ensures that the analysis establishing Properties
(1) and (2) becomes similar to the analyses of known dual polynomials for the OR function [46, 19].
In more detail, our prior work [19] built on work of Špalek [46] to give a dual witness γ for the fact
f (ORn ) = Ω(√n) for any constant ε < 1; moreover, γ places non-zero weight only on sets Hk ,
that deg ε
for values of k equal (up to scaling factors) to perfect squares. The pure high degree of γ is shown to be
equal to (at least) the number of sets Hk upon which γ places non-zero weight.
Call an input x ∈ {−1, 1}n valid if it is in Rm,a,b for some valid triple (m, a, b). By analogy with γ,
the dual witness φ that we construct in Stage 1 places weight only on inputs x ∈ Tk for divisors k of N
that are also (up to scaling factors) perfect squares. In particular, our definition of φ ensures that
φ (x) = 0 for all invalid inputs x . (2.3)
We are able to combine (2.3) with Lemma 2.4 and a basic combinatorial identity (cf. Lemma 3.2) to
show that the pure high degree of φ is at least |S|, where S denotes the set of Tk ’s upon which φ places
non-zero weight. In more detail, given any polynomial p of degree at most |S|, Lemma 2.4 gives us a
measure of control over p’s value on valid inputs. Lemma 2.4 provides no control over p’s value on
invalid inputs, but this is rendered irrelevant by (2.3), which guarantees that φ essentially ignores such
inputs.
Moreover, our definition of φ is carefully chosen to ensure that its correlation with ColN,R is large;
the precise calculation is closely analogous to the analysis from [46, 19] showing that γ is well-correlated
with the OR function [46, 19].
Overview of the second stage. In the second stage, we construct a dual polynomial ψ that exhibits
the optimal Ω(N 1/3 ) lower bound. Rather than only weighting inputs in Tk for some some divisors k of
N, ψ weights inputs in Rm,a,b for many valid triples (m, a, b). There are two key ideas that go into the
construction of ψ.
The first idea is to define ψ as the sum of two simpler dual polynomials ψ1 and ψ2 , each with pure
high degree Ω(N 1/3 )—then the sum ψ also has pure high degree Ω(N 1/3 ) (see Lemma 4.5). The first
polynomial ψ1 places a large constant fraction (close to 1/2) of its L1 mass on T1 , whereas ψ2 places a
large constant fraction of its L1 mass on T2 . Neither ψ1 nor ψ2 is well-correlated with ColN,R in the sense
of (2.3). However, they each place a constant fraction of their L1 mass on RN/2,2,1 , and they are designed
so that their values exactly cancel out on inputs in RN/2,2,1 . This allows us to show that ψ = ψ1 + ψ2
satisfies (2.3), even though ψ1 and ψ2 individually do not.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 9
M ARK B UN AND J USTIN T HALER
The second idea goes into the construction of ψ1 and ψ2 themselves. Specifically, we think of ψ1
and ψ2 as each being constructed in a two-step process. We focus on ψ1 in this discussion, since the
construction of ψ2 is similar. Very roughly speaking, in the first step, we consider a “polynomial” ψ 0 of
pure high degree Ω(N 1/3 ) that places a large constant fraction of its L1 mass on T1 ; the construction of ψ 0
is closely related to our construction of the simpler dual polynomial φ from Stage 1.
The reason we place the term “polynomial” in quotes above is that there is an important technical
caveat to our construction of ψ 0 : we think of ψ 0 as placing weight on sets RN/2,a,1 for many invalid triples
(N/2, a, 1), in addition to some valid ones. Of course, if (N/2, a, 1) is invalid, then RN/2,a,1 = 0, / so ψ 0
cannot place non-zero weight on the set. To address this issue, in Step 2, we add to ψ 0 a sequence of
00
polynomials ψN/2,a,1 00
, each of pure high degree Ω(N 1/3 ). For each invalid triple (N/2, a, 1), ψN/2,a,1 is
0
specifically constructed to cancel out the weight that ψ “places” on RN/2,a,1 .
Analogously to how our constructions of φ and ψ 0 were closely related to the dual witness for OR
00
constructed in our earlier work [19], our construction of ψN/2,a,1 is closely related to a dual witness η
for the Majority function, MAJ, that we constructed in the same work. Each ψN/2,a,1 00 places additional
non-zero mass on (non-empty) sets of the form Rm,a,1 for some a 6= 1 and m ∈ [N], but we are able to
show that the total mass placed on such sets is small, using an analysis closely related to the analysis of η
from [19]. Hence we are able to show that
ψ1 = ψ 0 + ∑ 00
ψN/2,a,1
invalid triples (N/2,a,1)
still places a large constant fraction of its L1 mass on T1 .
2.6 Discussion
On Kutin’s second step. Our construction of the optimal dual witness ψ for the C OLLISION func-
tion mimics the second step of Kutin’s symmetrization argument in three important ways described
below. We find this mimicry to be somewhat surprising—in our earlier work [19], we constructed an
optimal dual polynomial for symmetric Boolean functions that bore little relation to Paturi’s well-known
symmetrization-based proof of the same result [32]. We believe that this mimicry sheds new light, or at
least gives a new perspective, on why Kutin’s proof takes the structure that it does.
Recall that the second step of Kutin’s proof (cf. Section 2.4) proceeds via a case analysis. The
first “branch” in the case analysis depends on whether the expected value of the assumed n-variate
approximation p to ColN,R on the set RN/2,2,1 is large or small. This is mimicked in our construction of ψ
as a sum of two dual polynomials ψ1 and ψ2 , both of which individually place a lot of weight on RN/2,2,1 ,
but whose sum places zero weight on RN/2,2,1 .
The second “branch” in Kutin’s case analysis depends on whether |P(N/2, a, 1)| or |P(N/2, 2, b)| is
small for all a, b ≤ N 2/3 . He needs to consider this second branch because P(m, a, b) is not guaranteed to
be bounded for invalid triples (m, a, b).
This branch is mimicked in our construction of ψ1 (respectively, ψ2 ) as the sum of a single “polyno-
mial” ψ 0 that tries to place weight on sets RN/2,a,1 for invalid triples (N/2, a, 1) (respectively, (N/2, 2, b)),
and many other polynomials ψN/2,a,1 00 00
(respectively, ψN/2,2,b ), one for each invalid triple (N/2, a, 1) (re-
00
spectively, (N/2, 2, b)). In our dual setting, the reason we need to incorporate the polynomials ψN/2,a,1 is
0
to cancel out the weight that ψ tries to place on invalid sets RN/2,a,1 .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 10
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Finally, recall that Kutin applied Markov’s inequality from approximation theory in two of the four
cases considered in his analysis, and Bernstein’s inequality in the other two cases. Markov’s inequality
underlies Nisan and Szegedy’s standard symmetrization-based proof that the approximate degree of OR
√
is Ω( n) [30], while Berstein’s inequality underlies Paturi’s proof that the approximate degree of MAJ
is Ω(n) [32]. This is mimicked in our construction of ψ1 and ψ2 as the sum of ψ 0 and the ψN/2,a,1
00 and
00 0
ψN/2,2,b polynomials: the construction of ψ is closely analogous to the dual witness for OR from [19],
00
while the construction of the ψN/2,a,1 00
and ψN/2,2,b polynomials is based on the dual witness for MAJ
from [19].
On the first step, or why k-to-1 inputs matter. As noted by several authors (e. g., [2, Slide 36]), the
most miraculous element of the symmetrization-based proof of the C OLLISION lower bound is the first
step (cf. Lemma 2.4). The crux of this step is to establish, roughly speaking, that for any n-variate
polynomial p of total degree d, the function
P(k) := Ex∈Tk [p(x)]
is a polynomial in k of degree at most d. Why should this hold? More basically, why should inputs that
are k-to-1 even play a prominent role in the proof?
We provide some partial intuition for this in Section 6. Specifically, we explain that there is an
(asymptotically) optimal approximation p for ColN,R such that k-to-1 inputs correspond to constraints
that are made tight by the solution corresponding to p in the primal linear program of Section 2.2. Hence,
complementary slackness suggests that there should be a corresponding dual witness ψ that places weight
only on inputs that are k-to-1, or nearly so, justifying the prominent role that k-to-1 inputs play in both
the symmetrization-based proof and our new dual proof.
2.7 Formal statement of Lemma 2.4
Following Kutin [28], we define a special collection of functions which are a-to-1 on one part of the
domain and b-to-1 on the other part. For N > 0, recall that a triple of numbers (m, a, b) is valid if a | m
and b | (N − m). For each valid triple (m, a, b), we define
(
di/ae if 1 ≤ i ≤ m,
gm,a,b (i) =
R − b(N − i)/bc if m < i ≤ n.
Moreover, for each valid triple (m, a, b), we define a set Rm,a,b that is the orbit of gm,a,b under the
automorphism group SN × SR . Namely,
x ∈ Rm,a,b ⇐⇒ ∃σ ∈ SN , τ ∈ SR : τ ◦ gx ◦ σ = gm,a,b .
Note that the sets Rm,a,b are not uniquely determined; for instance Rm,1,1 = R0,a,1 = RN,1,b = T1 for every
m, a, b.
Lemma 2.5. Let p(x) be a real polynomial over {−1, 1}n of degree d. There is a trivariate polynomial P
of degree at most d with the property that for all valid triples (m, a, b),
P(m, a, b) = Ex∈Rm,a,b [p(x)] .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 11
M ARK B UN AND J USTIN T HALER
The statement of Lemma 2.5 differs slightly from the corresponding lemma in Kutin’s work [28]
(Lemma 2.7 below). Lemma 2.5 follows by combining Kutin’s formulation with the following simple
lemma from [20].
Lemma 2.6 ([20]). Let p be a polynomial over {−1, 1}n . Consider the map T : {−1, 1}n → {0, 1}N·R
defined by Ti j (x) = 1 if gx (i) = j, and Ti j (x) = 0 otherwise. Then there is a polynomial q : {0, 1}N·R → R
with deg q ≤ deg p, such that q(T (x)) = p(x) for all x ∈ {−1, 1}n .
Lemma 2.7 ([28]). Let q(t) be any degree d polynomial in the variables ti j . For a valid triple (m, a, b),
define Q(m, a, b) by
Q(m, a, b) = Ex∈Rm,a,b [q(T (x))] .
Then Q is a degree d polynomial in m, a, b.
p
3 An Ω( log N/ log log N) lower bound for the C OLLISION function
The following lemma is a refinement of [19, Proposition 14], which was used there to construct a
dual polynomial for OR. The function ω we construct here forms the core of the “first stage” of our
construction of a dual polynomial for the C OLLISION function.
Lemma 3.1. There exists a constant ζ > 0 such that for all δ ∈ (0, 1) and L ≥ 1, there is an explicit
ω : {1, . . . , L} → R with the following properties.
1−δ
1. ω(1) ≥ .
2
1−δ
2. −ω(2) ≥ .
2
L
3. ∑ |ω(k)| = 1.
k=1
√
4. For every polynomial p : {1, . . . , L} → R of degree d ≤ ζ δ L, we have ∑Lk=1 p(k)ω(k) = 0.
The proof will make use of the following simple combinatorial identity, a simple proof of which can
be found in [31, Appendix A].
Lemma 3.2. For any L > 0, let q : R → R be a univariate polynomial of degree strictly less than L. Then
L
L k
∑ (−1) k q(k) = 0 .
k=0
p
Proof of Lemma 3.1. Let c = d16/δ e. Let m = b (L − 1)/cc and define the set
T = {1} ∪ {ci2 : 0 ≤ i ≤ m} .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 12
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
p
Note that |T | = Ω( L/c). Define the function ω̂ : {0, 1, . . . , L} → R by
(−1)k · cm (m!)2
if k ∈ T ,
L c (m!)2 j∈T \{k} ( j − k)
m
∏
ω̂(k) = ∏ ( j − k) =
k L! j∈[[L]]\T
0 otherwise.
It is easy to check that ω̂(0) = 1.
For k = 1, we have
cm (m!)2
|ω̂(1)| = .
∏m 2
i=1 (ci − 1)
Notice that the magnitude |ω̂(1)| is tightly controlled:
m
cm (m!)2 i2
1≤ = ∏
∏m 2
i=1 (ci − 1)
2
i=1 i − 1/c
m
1
= ∏ 1+ 2
i=1 ci − 1
!
m
2
≤ exp ∑ 2
i=1 ci
3
≤ e8/c ≤ 1 + δ .
2
Here, we have used the fact that ∏m m
i=1 (1 + ai ) ≤ exp(∑i=1 ai ) for nonnegative ai . On the other hand, for
k = c`2 with ` > 0, we may write |ω̂(k)| as
cm (m!)2 (m!)2
=
(c`2 − 1) ∏i∈[[m]]\{`} |ci2 − c`2 | (c`2 − 1) ∏i∈[[m]]\{`} (i + `)|i − `|
2(m!)2
=
(c`2 − 1)(m + `)!(m − `)!
2
≤ 2 ,
c` − 1
where the last inequality follows because
(m!)2 m m−1 m−`+1
= · ·····
(m + `)!(m − `)! m + ` m + ` − 1 m+1
is a product of factors that are each smaller than 1. Thus, the total contribution of terms excluding 0 and 1
to the L1 norm of ω̂ is at most
m ∞
2 4 8 δ
∑ ci2 − 1 ∑ ci2 < c ≤ 2 .
<
i=1 i=1
Now define ω : {1, . . . , L} → R via
ω(k) = (−1)k−1 ω̂(k − 1)/kω̂k1 .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 13
M ARK B UN AND J USTIN T HALER
Then
1 1 1−δ
−ω(2) ≥ ω(1) ≥ ≥ ≥ .
1 + |ω̂(1)| + δ /2 2 + 2δ 2
This yields the first two claims about ω. The third claim follows immediately from the definition. Finally,
let p be a polynomial of degree strictly less than |T | − 1. Then
L L−1 L−1
L c (m!)2
m
k k L
∑ p(k)ω(k) = ∑ (−1) · k · L!kω̂k1 · p(k + 1) · ∏ ( j − k) = ∑ (−1) k q(k) , (3.1)
k=1 k=0 j∈[[L]]\T k=0
where
cm (m!)2
q(k) = · p(k + 1) · ∏ ( j − k)
L!kω̂k1 j∈[[L]]\T
is a polynomial of degree less than L. Since q(L) = 0, the right hand side of (3.1) is zero by Lemma 3.2.
This gives the last claim.
Our prior work [19], building on work of Špalek [46], obtained a dual polynomial γ for ORL by
setting the total weight of γ on inputs in Hk (the set of inputs of Hamming weight k) to be ω(k + 1). In
that work, the first three properties of ω√ensured that γ had high correlation with OR, while the fourth
ensured that it had pure high degree Ω( L).
Analogously, our dual polynomial φ for ColN,R below sets the total weight of φ on Tk to be ω(k). Then
again, the first three properties√ of ω ensure that φ is well-correlated with ColN,R , and the fourth ensures
that it has pure high degree Ω( L). However, we face the complication that Tk must be non-empty, i. e.,
k must divide N, for every k in the support of ω.pTo handle this complication, we take N large enough so
that all k = 1, 2, . . . , L divide N, yielding an Ω( log N/ log log N) lower bound.
Theorem 3.3. Let N =√ L. For δ > 0, there exists an explicit (1 − 2δ , d) dual polynomial φ
L! for somep
for ColN,R with d = Ω( δ L) = Ω( δ log N/ log log N).
Proof. First, notice that k | N for all k ∈ [L], so Tk 6= 0/ for every such k. Define φ (x) = ω(k)/|Tk | if x is in
Tk for some k ∈ [L], and φ (x) = 0 otherwise, where ω is obtained by applying Lemma 3.1. Note that φ (x)
is well-defined since |Tk | 6= 0 for all k ∈ [L], and each x ∈ {−1, 1}n is in Tk for at most one value of k.
We check
∑ φ (x) − ∑ φ (x) = ω(1) − ω(2) ≥ 1 − δ ,
x∈T1 x∈T2
where the inequality holds by Parts 1 and 2 of Lemma 3.1. Moreover,
L
∑ |φ (x)| = ∑ |ω(k)| ≤ δ ,
x∈B k=3
where the inequality holds by combining Parts 1-3 of Lemma 3.1. Thus,
∑ φ (x) − ∑ φ (x) − ∑ |φ (x)| ≥ 1 − 2δ .
x∈T1 x∈T2 x∈B
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 14
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Second,
L
∑ |φ (x)| = ∑ |ω(k)| = 1 ,
x∈T1 ∪T2 ∪B k=1
where the final equality
√ holds by Part 3 of Lemma 3.1.
Finally, let d = ζ δ L where ζ is as in the statement of Lemma 3.1, and let S ⊆ [n] with |S| ≤ d. We
must show that ∑x∈T1 ∪T2 ∪B φ (x)χS (x) = 0. Note that
L L L
∑ φ (x)χS (x) = ∑ ∑ φ (x) · χS (x) = ∑ ∑ (ω(k)/|Tk |) · χS (x) = ∑ ω(k) · Ex∈Tk [χS (x)] ,
x∈T1 ∪T2 ∪B k=1 x∈Tk k=1 x∈Tk k=1
where the first equality holds because φ (x) = 0 if x is not in Tk for some k ∈ [L].
By Lemma 2.5, there is a trivariate polynomial P of total degree at most d such that
P(m, a, b) = Ex∈Rm,a,b [χS (x)]
for all valid triples (m, a, b). In particular, since k | N for all k ∈ [L], q(k) := P(N, k, 1) is a univariate
polynomial in k such that q(k) = Ex∈Tk [χS (x)] for all k ∈ [L]. Hence, Part 4 of Lemma 3.1 implies that
L
∑ ω(k) · Ex∈T [χS (x)] = 0 .
k
k=1
4 An Ω(N 1/3 ) lower bound for the C OLLISION function
We now complete the “second stage” of our construction. The following lemma is a refinement of [19,
Proposition 10], which constructed an explicit dual polynomial for MAJ.
Lemma 4.1. There exists a constant ρ > 0 for which the following holds. Let δ ∈ (0, 1), N > 0 an even
integer, and k ∈ [N]. Then there is an explicit ηk : [[N]] → R such that
1. ηk is supported on {2k, 4k, . . . , 2bN/2kck} ∪ {N/2},
2. ηk (N/2) > (1 − δ )/2,
3. ∑Nr=0 |ηk (r)| = 1,
√
4. for every polynomial p : {0, . . . , N} → R of degree d ≤ ρ δ N/k, we have ∑Nr=0 p(r)ηk (r) = 0.
Proof. Throughout the proof, we assume for simplicity that N/2 is not a multiple of 2k. The analysis
when N/2 is a multiple
√ of 2k is similar.
Let c = d10/ δ e and t = 2bN/(4k)ck and define the set
S = {t ± 2c`k : 0 ≤ ` ≤ bt/(2ck)c} .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 15
M ARK B UN AND J USTIN T HALER
Note that |S| = Ω(N/ck). We claim that
πS (i) := ∏ | j − i|
j∈S, j6=i
is minimized at i = t. Notice that translating all points in S by a constant t does not affect πS−t (i − t),
and scaling all points in S by a constant a does not affect argmini πaS (i). Thus, it is enough to show
that πS∗ (i) is minimized at i = 0 for the set S∗ = {±` : ` ≤ q}. In this case, πS∗ (i) takes the simple form
(q − i)!(q + i)!, and we see that for all i ∈ S∗ ,
πS∗ (0) (q!)2 q q−1 q − |i| + 1
= = · ·····
πS∗ (i) (q − i)!(q + i)! q + |i| q + |i| − 1 q+1
is a product of terms smaller than 1, so πS∗ (i) is indeed minimized at i = 0.
Now let T = S ∪ {t − 2k, N/2} and define the function
( (−1)r (2ck)2h (h!)2 (2k)(N/2−t)
N (2ck)2h (h!)2 (2k)(N/2 − t) if r ∈ T ,
∏ j∈T \{r} ( j−r)
η̂(r) =
r N! ∏ ( j − r) =
j∈[[N]]\T 0 otherwise,
where h = bt/2ckc. The normalization is chosen so that |η̂(t)| = 1.
The reason that we include both (r − (t − 2k)) and (r − (N/2)) in the denominator of η̂ is to ensure
that the rate of decay of η̂(r) is at least quadratic as r moves away from t. This will ultimately allow us
to show that a large fraction of the `1 mass of η̂ comes from the point r = N/2.
For r = t − 2k, the mass |η̂(r)| is
(2ck)2h (h!)2 (2k)(N/2 − t) (N/2 − t) h
1
= ∏ 1 + (c`)2 − 1
2k(N/2 − t + 2k) ∏h`=1 (2ck` − 2k)(2ck` + 2k) N/2 − t + 2k `=1
!
h
1 2
≤ exp ∑ 2 2
2 `=1 c `
2
1 π
≤ exp
2 3c2
1+δ
< ,
2
where the first inequality holds because N/2 − t ≤ 2k, combined with the fact that ∏h`=1 (1 + a` ) ≤
exp(∑h`=1 a` ) for nonnegative a` .
For r = N/2, we may calculate
(2ck)2h (h!)2 (2k)(N/2 − t)
|η̂(r)| =
(N/2 − t)(N/2 − t + 2k) ∏h`=1 (2ck` + (N/2 − t))(2ck` − (N/2 − t))
h
(2ck`)2
2k 1
= ∏ 2 2
≥ .
N/2 − t + 2k `=1 (2ck`) − (N/2 − t) 2
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 16
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Now we analyze the remaining summands, and show that their total contribution is much smaller
than 1. Recall that the choice i = t minimizes πS (i), and that πS (t) = (2ck)2h (h!)2 . Therefore,
(2ck)2h (h!)2 (2k)(N/2 − t) 2k(N/2 − t) 1
|η̂(t + 2ck`)| = ≤ ≤ 2 2 ,
∏ j∈T \{t+2ck`} | j − (t + 2ck`)| |2ck` + 2k| · |2ck` − (N/2 − t)| c ` − 1
where the final inequality exploits the fact that N/2 − t < 2k. Similarly,
(2ck)2h (h!)2 (2k)(N/2 − t) 2k(N/2 − t) 1
|η̂(t − 2ck`)| = ≤ ≤ 2 2 .
∏ j∈T \{t−2ck`} | j − (t − 2ck`)| |2ck` − 2k| · |2ck` + (N/2 − t)| c ` − 1
We can use this quadratic decay to bound the total L1 mass of the points outside of {t − k,t, N/2}.
1 2 π2 δ
∑ |η̂( j)| ≤ ∑ 2 2
≤ · < .
j∈S\{t} `6=0 (c ` − 1) c2 − 1 6 2
Now let ηk (r) = (−1)r+h+N/2 η̂(r)/kη̂k1 . Since η̂ is supported on T ⊆ {2k, 4k, . . . , 2bN/2kck} ∪
{N/2}, the function ηk is as well, giving the first claim. Moreover,
1/2 1−δ
ηk (N/2) ≥ ≥ .
(1/2 + δ /2) + 1/2 + δ /2 2
This yields the second claim about ηk . The third claim follows immediately from the definition. Finally,
let p be a polynomial of degree strictly less than |T |, where |T | ≥ ρN/k for a constant ρ. Then
N N
(−1)r+h+N/2 N (2ck)2h (h!)2 (2k)(N/2 − t)
∑ p(r)ηk (r) = ∑ p(r) kη̂k1 r N! ∏ ( j − r)
r=0 r=0 j∈[[N]]\T
N
r N
= ∑ (−1) q(r)
r=0 r
for a polynomial q of degree strictly less than N. This is equal to zero by Lemma 3.2, giving the final
claim.
We obtain our dual polynomial ψ for the ColN,R as a linear combination of two simpler functions ψ1
and ψ2 . The properties of these functions that we will need are captured in the following lemma.
Lemma 4.2. Let N > 0 be an integer multiple of 4. For R ≥ N, there exist explicit ψ1 , ψ2 : {−1, 1}n → R
and d = Ω(δ 1/3 N 1/3 ) such that
1−δ
1. ∑ ψ1 (x) > 2
,
x∈T1
1−δ
2. − ∑ ψ2 (x) > ,
x∈T2 2
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 17
M ARK B UN AND J USTIN T HALER
3. kψ1 k1 = kψ2 k1 = 1,
4. ∑x∈T2 |ψ1 (x)| = ∑x∈T1 |ψ2 (x)| = 0,
5. ψ1 , ψ2 have pure high degree at least d,
6. ∑x∈T1 ψ1 (x) = ∑x∈RN/2,2,1 ψ2 (x),
7. ∑x∈RN/2,2,1 ψ1 (x) = ∑x∈T2 ψ2 (x),
8. ψ1 and ψ2 are each constant on each set Rm,a,b when (m, a, b) is valid.
The functions ψ1 , ψ2 are themselves based on an intermediate construction of a function Ψ : [N] ×
[K] → R, for K = Θ(N 2/3 ), depicted pictorially in Figure 1 below. The function Ψ, defined in the proof
of Lemma 4.2, combines the constructions of ω from Lemma 3.1 and ηk from Lemma 4.1.
Figure 1: A visualization of the support of the function Ψ(m, k), for N = 360 and K = 64. The horizontal
axis represents values of k = 1, . . . K and the vertical axis represents values of m = 1, . . . , N. Red dots
indicate values in the support of the function ω(k)1m=N/2 , while blue dots indicate values in the support
of the function ω(k)ηk (m)1k≥3 . When red dots and blue dots overlap, they “cancel out,” in the sense that
a point with both a red and a blue dot is not in the support of Ψ.
Together, the functions ψ1 , ψ2 yield the desired dual polynomial for ColN,R .
Theorem 4.3. Let N > 0 be an integer multiple of 4. For R ≥ N, there exists an explicit (1 − 6δ , d)-dual
polynomial ψ for ColN,R for d = Ω(δ 1/3 N 1/3 ).
Remark 4.4. The dependence of the lower bound Theorem 4.3 on both parameters δ and N for 1/N ≤
δ ≤ 1/10, is tight up to a logarithmic factor in the size of the range. We show this in Section 7 by
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 18
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
constructing an explicit approximating polynomial for ColN,R of the appropriate degree, by building on
the ideas underlying the quantum query algorithm of Brassard et al. [17].
Proof of Theorem 4.3, assuming Lemma 4.2. Let
a = ∑ ψ1 (x)
x∈T1
and let
b = ∑ |ψ2 (x)| = − ∑ ψ2 (x),
x∈T2 x∈T2
where ψ1 and ψ2 are as in Lemma 4.2. Let ψ(x) = aψ1 (x) + bψ2 (x). By Property 5 of Lemma 4.2 and
Lemma 4.5 below, ψ also has pure high degree at least d. So we need only show that ψ has correlation at
least 1 − 6δ with ColN,R . To this end, note the following.
(1 − δ )2
1. ∑ ψ(x) = a2 > 4
. This inequality uses Properties 1 and 4 of Lemma 4.2.
x∈T1
(1 − δ )2
2. − ∑ ψ(x) = b2 > . This inequality uses Properties 2 and 4 of Lemma 4.2.
x∈T2 4
3. ∑ |ψ(x)| ≤ a ∑ |ψ1 (x)| + b ∑ |ψ2 (x)| ≤ (a + b)δ .
x∈B x∈B\RN/2,2,1 x∈B\RN/2,2,1
Here, the first inequality exploits the fact that
∑ |ψ(x)| = ∑ |a · ψ1 (x) + b · ψ2 (x)| = 0 . (4.1)
x∈RN/2,2,1 x∈RN/2,2,1
The last equality in (4.1) holds because, for all x ∈ RN/2,2,1 ,
! !
a · ψ1 (x) + b · ψ2 (x) = ∑ ψ1 (x0 ) · ψ1 (x) + − ∑ ψ2 (x0 ) ψ2 (x)
x0 ∈T1 x0 ∈T2
= ∑ ψ2 (x0 ) · ψ1 (x) + − ∑ ψ1 (x0 ) ψ2 (x)
x0 ∈R N/2,2,1 x0 ∈R N/2,2,1
1
= ∑ ψ2 (x0 ) ψ1 (x0 )+
x0 ∈RN/2,2,1 |RN/2,2,1 | x0 ∈R∑
N/2,2,1
1
− ∑ ψ1 (x0 ) ψ2 (x0 )
x0 ∈RN/2,2,1 |RN/2,2,1 | x0 ∈R∑
N/2,2,1
= 0,
where the second equality used Properties 6 and 7 of Lemma 4.2, and the last equality used Property
8.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 19
M ARK B UN AND J USTIN T HALER
Thus, the correlation of ψ with ColN,R is
∑ ψ(x) − ∑ ψ(x) − ∑ |ψ(x)| ≥ a2 + b2 − (a + b)δ
x∈T1 x∈T2 x∈B
1
≥ − 2δ ≥ (1 − 6δ ) · kψk1 ,
2
where the final inequality holds because kψk1 ≤ a2 + b2 + (a + b)δ ≤ 1/2 + δ .
Lemma 4.5. Let ψ1 , ψ2 : {−1, 1}n → {−1, 1} each have pure high degree at least d. Then ψ = ψ1 + ψ2
also has pure high degree at least d.
Proof. Let S ⊆ [n] with |S| ≤ d. Then
∑ ψ(x)χS (x) = ∑ ψ1 (x)χS (x) + ∑ ψ2 (x)χS (x) = 0 .
x∈{−1,1}n x∈{−1,1}n x∈{−1,1}n
What now remains is to prove Lemma 4.2, i. e., to construct the intermediate functions ψ1 , ψ2 that
were used to prove Theorem 4.3.
Proof of Lemma 4.2. Let ζ be the constant from Lemma 3.1, let ρ be the constant from Lemma 4.1, and
let δ 0 = 1/2. Set
2/3 1/3
δ0
ρN 1
K=2 and let d = ρ 1/3 ζ 2/3 (δ 0 )1/6 δ 1/3 N 1/3 = Ω(δ 1/3 N 1/3 ) ,
ζ δ 2
noting that d ≤ ζ (δ /8)1/2 K 1/2 and d ≤ ρ(δ 0 )1/2 N/k for every k ≤ K. Let ω : {1, . . . , K} → R, with
correlation constant δ /8, and η3 , . . . , ηK : {1, . . . , N} → R, with correlation constant δ 0 , be as in the
conclusions of those lemmas.
We start by defining a function Ψ : [N] × [K] → R as follows.
ω(k)
Ψ(m, k) = ω(k) · 1m=N/2 − 1k≥3 · ηk (m) .
ηk (N/2)
Here, ( (
1 if m = N/2, 1 if k ≥ 3,
1m=N/2 = and 1k≥3 =
0 otherwise, 0 otherwise.
To help the reader build intuition about the function Ψ, we present in Figure 1 a visualization of its
support.
We first show how to use Ψ to construct the polynomial ψ1 . Analogously to our construction of φ ,
we want ψ1 to place a total weight of Ψ(m, a) on each set Rm,a,1 . Recall from our overview in Section 2.5
that we think of
ψ1 = ψ 0 + ∑ 00
ψN/2,a,1 ,
invalid triples (N/2,a,1)
where ψ 0 looks like the simpler “first stage” dual polynomial φ from our informal overview (which we
00
constructed in Section 3) and each ψN/2,a,1 cancels out the weight φ places on values of k the do not
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 20
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
divide N. This structure underlies our construction of Ψ, where we add multiples of the polynomials
ηk (m) to cancel out the weight ω(k) places on invalid triples.
Now we construct and analyze the polynomial ψ1 . Define
Ψ(m, k)/|Rm,k,1 | if x ∈ Rm,k,1 \ T1 ,
ψ̂1 (x) = Ψ(N/2, 1)/|T1 | if x ∈ T1 ,
0 otherwise.
Notice that ψ̂1 is well-defined, because any x 6∈ T1 is in Rm,k,1 for at most one triple (m, k, 1). We collect
several calculations with ψ̂1 . First,
1 − δ /8
∑ ψ̂1 (x) = Ψ(N/2, 1) = ω(1) > 2
,
x∈T1
1 − δ /8
− ∑ ψ̂1 (x) = −Ψ(N/2, 2) = −ω(2) > ,
x∈RN/2,2,1 2
and
∑ |ψ̂1 (x)| = ∑ |Ψ(m, k)|
x∈B\RN/2,2,1 {(m,k) : k|m}\{(N/2,1),(N/2,2)}
K
ω(k) bN/2kc
=∑ ∑ |ηk (2ki)|
k=3 ηk (N/2) i=1
K
≤ 4 ∑ |ω(k)|
k=3
δ
≤ ,
2
where the penultimate inequality exploits Properties 2 and 3 of Lemma 4.1, and the final inequality
exploits Properties 1-3 of Lemma 3.1.
Noting that |ω(1)| + |ω(2)| ≤ 1, it follows that kψ̂1 k1 ≤ 1 + δ /2. So setting ψ1 = ψ̂1 /kψ̂1 k1 , it is
immediate that ψ1 satisfies the first three properties in the statement of the lemma. ψ1 also satisfies the
fourth property, since for any x ∈ T2 , ψ1 (x) = Ψ(N, 2)/|T2 | = 0.
Now we will show that ψ̂1 , and hence ψ1 , has pure high degree at least d. We require two observations.
a) Ψ is supported on (m, k) for which k | m. To see this, note first that for any k ≥ 3,
ω(k)
Ψ(N/2, k) = ω(k) − · ηk (N/2) = 0 .
ηk (N/2)
The claim now follows from Property 1 of Lemma 4.1, combined with the fact that 2 | N.
b) Ψ(m, 1) is nonzero only for m = N/2, and hence
N
∑ ψ̂1 (x) = Ψ(N/2, 1) = ∑ Ψ(m, 1) .
x∈T1 m=1
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 21
M ARK B UN AND J USTIN T HALER
Fix any S ⊆ [n] with |S| ≤ d. Let Q(m, k) be a polynomial of degree at most d in each variable such
that, for all pairs (m, k) with k | m,
Q(m, k) = Ex∈Rm,k,1 [χS (x)] .
The existence of such a bivariate polynomial Q is guaranteed by Lemma 2.5. Then the previous two
observations together imply that
N N
∑ ψ̂1 (x)χS (x) = ∑ ∑ Ψ(m, k)Q(m, k) . (4.2)
x∈{−1,1}n m=1 k=1
We remark that a key point is the derivation of (4.2) is that we have no control over the evaluations
Q(m, k) when k does not divide m, yet this is rendered irrelevant because Ψ(m, k) = 0 for all such pairs.
The right hand side of (4.2) equals
!
K K bN/2kc
ω(k)
∑ ω(k)Q(N/2, k) − ∑ ηk (N/2) ηk (N/2)Q(N/2, k) + ∑ ηk (2ik)Q(2ik, k) . (4.3)
k=1 k=3 i=1
The first sum in (4.3) is zero by Lemma 3.1 since Q(N/2, k) is a polynomial of degree at most d in k.
The second sum is also zero because for each fixed k, Q(r, k) is a polynomial of degree at most d in the
variable r, and hence the term in parentheses is zero by Lemma 4.1 (Parts 1 and 4). Thus ψ̂1 has pure
high degree at least d.
The construction of ψ2 is similar. This time, we let
Ψ(m, k)/|Rm,k,2 | if x ∈ Rm,k,2 \ T2 ,
ψ̂2 (x) = Ψ(N/2, 2)/|T2 | if x ∈ T2 ,
0 otherwise.
Note that ψ̂2 is well-defined, because any x 6∈ T2 is in Rm,k,2 for at most one triple (m, k, 2). We define
ψ2 = ψ̂2 /kψ̂2 k1 . Showing that ψ2 satisfies Properties 1-4 of the lemma follows from the same calculations
we used for ψ1 .
To show that ψ2 has pure high degree at least d, we require the following additional observations.
c) Ψ is supported on pairs (m, k) for which k | m and 2 | (N − m). To see the latter property, note that if
Ψ(m, k) 6= 0, then m is even (this holds because N/2 is even, which follows from our requirement that
N is a multiple of 4), and hence N − m is as well.
d) Ψ(m, 2) is nonzero only for m = N/2. It follows that ∑x∈T2 ψ̂2 (x) = Ψ(N/2, 2) = ∑Nm=1 Ψ(m, 2).
With these observations in hand, showing that ψ2 has pure high degree d then follows from calculations
analogous to the ones we used for ψ1 .
Finally, the fact that ψ1 and ψ2 satisfy Properties 6, 7, and 8 of the lemma follows from their
definitions, combined with the fact that RN/2,1,2 = RN/2,2,1 . In fact, ∑x∈T1 ψ1 (x) equals Ψ(N/2, 1), while
∑ ψ2 (x)
x∈RN/2,2,1
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 22
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
also equals Ψ(N/2, 1), giving Property 6. Similarly, ∑x∈T2 ψ2 (x) equals Ψ(N/2, 2), while
∑ ψ1 (x)
x∈RN/2,1,2
also equals Ψ(N/2, 1). This completes the proof.
5 A dual polynomial for E LEMENT D ISTINCTNESS
In this section, we give a generic construction showing how to transform any dual polynomial for
C OLLISION into a dual polynomial for E LEMENT D ISTINCTNESS.
We first recall the reduction from C OLLISION to E LEMENT D ISTINCTNESS given in [5].4 The
reduction shows how to turn a polynomial p approximating EDM,R into a polynomial q approximating
ColN,R , with N ≈ M 2 and deg q ≤ deg p.
We illustrate the reduction for N = M 2 /12. Let p : {−1, 1}m → {−1, 1} be an (1/6)-approximation
of EDM,R , with m = M log R. Define a polynomial q : {−1, 1}n → {−1, 1} for n = N log R by
1
q(y1 , . . . , yN ) = N
∑ p(yi1 , yi2 , . . . , yiM ) .
M 1≤i1 <i2 <···<iM ≤N
That is, q(y) is the expected value of p(x) where x is the concatenation of a random subset of M of the
blocks y1 , . . . , yN . To simplify notation, for a set S = {i1 , i2 , . . . , iM }, let y|S = (yi1 , yi2 , . . . , yiM ). Note that
deg q ≤ deg p. Moreover, since q is an average of values in [−7/6, 7/6], it is always in [−7/6, 7/6] itself.
To finish arguing that q is a (1/3)-approximation to ColN,R , we consider two cases.
1. If y ∈ T1 , i. e., y is a 1-to-1 input, then y|S is always 1-to-1. Hence p(y|S ) ∈ [5/6, 7/6] for every
subset of indices, so q(y) ∈ [2/3, 4/3].
2. If y ∈ T2 , i. e., y is a 2-to-1 input, then with high probability y|S is not 1-to-1. This follows from the
“birthday bound”:
1
Pr [ED(y|S ) = 1] ≤ exp(−M 2 /4N) ≤ .
|S|=M 12
Therefore, q(y) ≤ (11/12)(−5/6) + (1/12)(7/6) ≤ −2/3.
The construction we give in this section takes a dual view of the reduction above. Namely, we show
how to transform a dual polynomial ψ for ColN,R into a dual polynomial ϕ for EDM,R , with M 2 ≈ N. In
the primal reduction, we constructed q(y) from p(x) by averaging p over all subsets of size M. The right
analogue in the dual reduction is to construct ϕ(x) by averaging ψ(y) over a carefully constructed set of
extensions from x to a longer input y. In particular, ϕ(x) averages ψ(y) over all y for which x could have
been produced by taking a subset of M blocks of y.
We give this reduction formally below.
4 While the reduction given in Aaronson and Shi’s paper is stated in terms of quantum query algorithms, it is straightforward
to rephrase the reduction in terms of approximating polynomials instead.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 23
M ARK B UN AND J USTIN T HALER
Theorem 5.1. Let ψ : {−1, 1}n → {−1, 1} be a (1 − δ , d)-dual polynomial for ColN,R . Then ψ can
m
pto construct ϕ : {−1, 1} → {−1, 1} that is an (1 − 2δ , d)-dual polynomial for EDM,R when
be used
M ≥ 2 N log(2/δ ).
Corollary 5.2. For any δ > 0, there is an explicit (1 − δ , d)-dual polynomial for EDM,R with
1/3 !
δ 2/3
d=Ω M .
log(1/δ )
Remark 5.3. The dependence of Corollary 5.2 on δ is essentially tight for δ = O(M −2 ). See Section 7
for details.
Proof of Theorem 5.1. Given a set S = {i1 , . . . , iM } ⊂ [N] with i1 < i2 < · · · < iM and a bit string y =
(y1 , . . . , yN ) ∈ {−1, 1}n , define the restriction of y to the set S, denoted by y|S ∈ {−1, 1}m , to be the string
of length m = M log R obtained by concatenating the blocks yi for i ∈ S, i. e., y|S = (yi1 , yi2 , . . . , yiM ). Given
N
a bit string x ∈ {−1, 1}m , define the multiset of extensions of x, denoted by ext(x), to be the M RN−M
n
strings y ∈ {−1, 1} where y|S = x for some |S| = M. Restrictions and extensions are related by the
equality of the multisets
{(x, y) : x ∈ {−1, 1}m , y ∈ ext(x)} = {(x, y) : y ∈ {−1, 1}n , x = y|S for some |S| = m} . (5.1)
For x ∈ {−1, 1}m , define the polynomial
1
ϕ(x) = N
∑ ψ(y) .
M y∈ext(x)
/ {−1, 1}m . We claim that ϕ is a good dual polynomial for the E LEMENT D ISTINCT-
Let ϕ(x) = 0 for x ∈
NESS function ED, which requires us to show
1. ∑x∈{−1,1}m ϕ(x) ED(x) > (1 − 2δ ) · ∑x∈{−1,1}m |ϕ(x)|, and
2. ∑x∈{−1,1}m ϕ(x)χS (x) = 0 for all |S| ≤ d.
To verify the first property, define
1
A(y) = N
∑ ED(y|S ) .
M |S|=M
We collect a few observations about A.
1. |A(y)| ≤ 1 for all y.
2. If y ∈ T1 , then A(y) = 1.
3. If y ∈ T2 , then
Pr [ED(y|S ) = 1] ≤ exp(−M 2 /4N) .
|S|=M
Hence,
A(y) ≤ −1 + 2 exp(−M 2 /4N) ≤ −1 + δ .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 24
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Therefore we get
1
∑ ϕ(x) ED(x) = N
∑ ψ(y) ED(x)
∑
x∈{−1,1}m M x∈{−1,1}m y∈ext(x)
1
= N
∑ ψ(y) ED(y|S )
∑ by (5.1)
M y∈{−1,1}n |S|=M
= ∑ A(y)ψ(y) by definition of A.
y∈{−1,1}n
By observations (1)-(3) about A, this expression is
!
≥ ∑ ψ(y) − ∑ ψ(y) − ∑ |ψ(y)| − δ ∑ |ψ(y)|
y∈T1 y∈T2 y∈B y∈T2
≥ (1 − 2δ ) ∑ |ψ(y)| as ψ is a dual polynomial for ColN,R
y∈{−1,1}n
1
= (1 − 2δ ) ∑ N
∑ |ψ(y)|
y∈{−1,1}n M |S|=M
1 − 2δ
≥ N
∑ ∑ |ψ(y)| by (5.1)
M x∈{−1,1}m y∈ext(x)
≥ (1 − 2δ ) ∑ |ϕ(x)| .
x∈{−1,1}m
For the second property, let T be a subset of [N] with |T | ≤ d. Then
1
∑ ϕ(x)χT (x) = N
∑ ψ(y)χT (x)
∑
x∈{−1,1}m M x∈{−1,1}m y∈ext(x)
1
= N
∑ ∑ ψ(y)χT (y|S ) by (5.1)
M |S|=M y∈{−1,1}n
1
= N
∑ ∑ ψ(y)χT |S (y)
M |S|=M y∈{−1,1}n
= 0,
where T |S denotes the subset of T contained in the blocks specified by S.
6 On complementary slackness
Recalling that any bounded-error quantum query algorithm can be converted into an approximating
polynomial [11], the collision-finding algorithm of Brassard, Høyer, and Tapp [17] yields an explicit,
asymptotically optimal approximating polynomial for ColN,R . We describe this polynomial p below.
Recall that any approximating polynomial for ColN,R represents a feasible solution to the primal
linear program considered in Section 2.2. If the polynomial p were an exactly optimal ε-approximation
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 25
M ARK B UN AND J USTIN T HALER
for ColN,R , then complementary slackness would imply that the optimal dual polynomial ψ for ColN,R is
supported on the points corresponding to constraints made tight by p. That is, ψ : {−1, 1}n → {−1, 1} is
supported on x ∈ {−1, 1}n for which |p(x) − Col(x)| = ε. We refer to these as the maximum-error points
of p.
While we do not know whether p is an exactly optimal approximating polynomial for ColN,R , we
might still expect that an approximate version of complementary slackness holds, in the sense that a
“good” dual polynomial should place all or most of its weight on points that are “nearly” maximum-error
points of p. Indeed, this intuition has proven accurate for all of the dual polynomials constructed in
prior work, including for symmetric functions (see [19, Section 4.5]), block-composed functions (see [48,
Section 1.2.4]), and the intersection of two majorities [41]. Below, we argue that k-to-1 inputs are nearly
maximum-error points for p, which explains why our dual polynomials for collision are supported on
inputs that are roughly k-to-1, in addition to why these inputs play a prominent role in the original
symmetrization-based proof.
An asymptotically optimal approximation p for ColN,R . For a subset S ⊂ [N], define
crossS : {−1, 1}n → R via
crossS (x1 , . . . , xN ) = |{i ∈ S, j ∈
/ S : xi = x j }| = ∑ EQ(xi , x j ) ,
i∈S, j6∈S
where EQ denotes the equality function. That is, crossS (x) counts the number of cross-collisions between
indices in S and indices outside of S. Notice that EQ(xi , x j ) is a function of only 2 · log R variables, and
hence crossS (x1 , . . . , xN ) is exactly computed by a polynomial of degree 2 · log R.
In addition, for a subset S ⊂ [N], define the function IED,S (x1 , . . . , xN ) to be 1 if xi 6= x j for all pairs
i, j ∈ S with i 6= j, and 0 otherwise. That is, IED,S indicates whether x is 1-to-1 on the indices in S. Notice
that IED,S is a function of only |S| · log R variables, and hence is exactly computed by a polynomial of
degree |S| · log R.
For the remainder of the discussion, let r = N 1/3 —we focus on the quantity crossS (x) when |S| = r.
We will need the following simple observations.
1. If x ∈ T1 , i. e., x is a 1-to-1 input, then crossS (x) = 0 and IED,S (x) = 1 for any S.
2. If x ∈ T2 , i. e., x is a 2-to-1 input, then IED,S (x) = 1 =⇒ crossS (x) = r.
3. If x ∈ T2 , then, over the random choice of S, IED,S (x) = 0 with probability at most (N/2) · (r/N)2 ≤
N −1/3 .
4. For all x ∈ {−1, 1}n , IED,S (x) = 1 =⇒ crossS (x) ≤ N − r.
Let Td : R → R denote the degree-d Chebyshev polynomial of the first kind. This polynomial has the
following properties.
a) Td (x) ∈ [−1, 1] for x ∈ [−1, 1].
b) Td (1 + M/d 2 ) ≥ 10 for a constant M independent of d.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 26
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
c) The extreme points of Td in [−1, 1] are the degree-d Chebyshev nodes, which take the form cos(iπ/d)
for 0 ≤ i ≤ d.
Truncating the Taylor expansion of cos(x) = 1 − x2 /2 + . . . after the quadratic term, one sees that the
Chebyshev nodes are well-approximated via the expression cos(iπ/d) ≈ 1 − (ci2 /d 2 ) for some constant
c.
Applying an appropriate affine transformation to Td , we obtain a polynomial Ad with the following
properties.
a) Ad (0) = 1.
b) Ad (i) ∈ [−1, −3/4] for all real numbers i ∈ [1, d 2 /M].
c) Ad (i) ∈ [−1, 1] for all real numbers i ∈ [0, d 2 /M].
d) The extreme points of Ad are well approximated by the points c · i2 for i ∈ {0, 1, . . . , bd · M −1/2 c}.
Let pS (x) = IED,S (x) · Ad (crossS (x1 , . . . , xN )/r) for d = 100 · M · N 1/3 , and let
1
p(x) = E|S|=r [pS (x)] = N
∑ pS (x) .
r |S|=r
Then p is a polynomial of degree |S| log R + 2 · d · log R = O(N 1/3 log R). We argue that p approximates
ColN,R to error ε for some ε ≤ 1/3. The analysis falls into three cases.
Case 1: For x ∈ T1 , pS (x) = Ad (0) = −1 for all S, where the first equality follows from Property 1 above.
So p(x) = E|S|=r [pS (x)] = 1.
Case 2: For x ∈ T2 , IED,S (x) = 1 =⇒ pS (x) = Ad (1) ∈ [−1, −3/4], where the equality follows from
Property 2 above. Meanwhile, IED,S (x) 6= 1 =⇒ pS (x) = 0. Combining these two facts with
Property 3 above establishes that p(x) = E|S|=r [pS (x)] ∈ [−1, −2/3].
Case 3: For x ∈ {−1, 1}n , pS (x) ∈ [−1, 1]. This follows from Property 4 above.
Identifying maximum-error points of p. For any fixed S, the maximum-error points of pS are well-
approximated by the x ∈ {1, 1}n for which the following two equations hold:
crossS (x) = c · i2 · r for some i ∈ {0, 1, . . . , bd · M −1/2 c} (6.1)
and
IED,S (x) = 1. (6.2)
(This follows from the fact that the extreme points of Ad are roughly of the form c · i2 for 0 ≤ i ≤ d · M −1/2 ).
However, the maximum-error points for the averaged polynomial p(x) = E|S|=r [pS (x)] are the points
x that satisfy (6.1) and (6.2) with high probability over the choice of S. Indeed, for these points x, the
error of p(x) is at least ε · (1 − o(1)) ≈ ε.
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 27
M ARK B UN AND J USTIN T HALER
Consider any k of the form k = c · i2 + 1 for some i ∈ {0, 1, . . . , bd · M −1/2 c}, such that k = o(N 1/3 ).
Consider any x ∈ Tk ; we claim that x satisfies (6.1) and (6.2) with probability 1 − o(1) over choice of S.
To see this, observe that the probability that IED,S (xS ) = 0 is at most (N/k) · k2 · (r/N)2 = k · r2 /N = o(1).
And if IED,S (xS ) 6= 0, then the number of cross-collisions is exactly
crossS (x1 , . . . , xN ) = r · (k − 1) .
When k takes the form k = c · i2 + 1, this means that x satisfies (6.1). Hence, x has nearly maximal error
even for the averaged polynomial p.
7 On the tightness of Theorem 4.3 and Corollary 5.2
To complement Theorem 4.3, we construct an approximating polynomial that gives a nearly matching
upper bound on the approximate degree of ColN,R . The construction is a refinement of the approximating
polynomial given in Section 6.
Proposition 7.1. For 0 ≤ δ ≤ 1/N, there exists a polynomial p of degree O(δ 1/3 N 1/3 log R) that (1 − δ )-
approximates ColN,R .
Proof sketch. See Section 6 for the construction of an approximating polynomial of degree O(N 1/3 log R)
in the case where δ is constant. In order to obtain an improved upper bound for vanishing δ , we make the
following changes to that construction.
1. We instead choose r = δ 1/3 N 1/3 . Now if x is a 2-1 input, the probability over the random choice
of the set S of obtaining a collision inside S, i. e., the probability that IED,S = 0, is at most
(N/2) · (r/N)2 ≤ δ /2.
2. We instead let Ad be an affine transformation of a Chebyshev polynomial with the following
properties for some constant M:
• Ad (0) ≥ δ /2,
• Ad (i) ∈ [−1, −δ /2] for i ∈ [1, d 2 /Mδ ],
• Ad (i) ∈ [−1, 1] for x ∈ [0, d 2 /Mδ ].
3. Setting d = 100 · M · r ensures that the polynomial p has degree O(δ 1/3 N 1/3 log R) and is a (1 − δ )-
approximation of ColN,R .
We now show that Corollary 5.2 is tight up to a factor of log R, when δ ≤ 1/M 2 . This gives mild
evidence that the lower bound has the right dependence on both parameters M, δ for vanishing δ .
Proposition 7.2. Let δ ≤ 1/M 2 . Then there exists a (1 − δ )-approximating polynomial for EDM,R with
degree O(log R).
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 28
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
Proof. We write ^
EDM,R (x1 , . . . , xM ) = NEQ(xi , x j ) ,
i6= j
where NEQ(xi , x j ) = 1 if i and inputs j are distinct, and is zero otherwise. The function NEQ can be
computed exactly by a polynomial of degree O(log R). Therefore, the polynomial
!
1 1
− NEQ(xi , x j )
M 2 i6∑
2 =j
has degree O(log R) and approximates EDM,R to within error 1 − 1/M 2 .
Acknowledgments. We are grateful to Guy Kindler, Yaoyun Shi, and Mario Szegedy for several
illuminating discussions during the early stages of this work. We thank Scott Aaronson and Emanuele
Viola for helpful comments on an earlier version of this manuscript. We also thank Sasha Sherstov and the
anonymous reviewers for additional helpful suggestions (including the suggestion to include Figure 1).
References
[1] S COTT A ARONSON: Quantum lower bound for the collision problem. In Proc. 34th STOC, pp.
635–642. ACM Press, 2002. [doi:10.1145/509907.509999] 2
[2] S COTT A ARONSON: The polynomial method in quantum and classical computing. In Proc. 49th
FOCS, p. 3. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.91] 2, 11
[3] S COTT A ARONSON: The collision problem: Notes for lecture 13 of MIT course 6.845: Quantum
complexity theory, 2010. Available at MIT OCW. 9
[4] S COTT A ARONSON: The collision lower bound after 12 years, 2013. Available on author’s website.
2
[5] S COTT A ARONSON AND YAOYUN S HI: Quantum lower bounds for the collision and the element
distinctness problems. J. ACM, 51(4):595–605, 2004. [doi:10.1145/1008731.1008735] 2, 4, 9, 23
[6] A NDRIS A MBAINIS: Quantum lower bounds by quantum arguments. J. Comput. System Sci.,
64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826, arXiv:quant-
ph/0002066] 5
[7] A NDRIS A MBAINIS: Polynomial degree and lower bounds in quantum complexity: Colli-
sion and element distinctness with small range. Theory of Computing, 1(3):37–46, 2005.
[doi:10.4086/toc.2005.v001a003, arXiv:quant-ph/0305179] 2, 3
[8] A NDRIS A MBAINIS: Polynomial degree vs. quantum query complexity. J. Comput. System
Sci., 72(2):220–238, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.06.006,
arXiv:quant-ph/0305028] 5
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 29
M ARK B UN AND J USTIN T HALER
[9] A NDRIS A MBAINIS: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–
239, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447311, arXiv:quant-
ph/0311001] 2
[10] H OWARD BARNUM , M ICHAEL E. S AKS , AND M ARIO S ZEGEDY: Quantum query complexity and
semi-definite programming. In Proc. 18th IEEE Conf. on Computational Complexity (CCC’03), pp.
179–193. IEEE Comp. Soc. Press, 2003. [doi:10.1109/CCC.2003.1214419] 5
[11] ROBERT B EALS , H ARRY B UHRMAN , R ICHARD C LEVE , M ICHELE M OSCA , AND RONALD
DE W OLF : Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary
version in FOCS’98. [doi:10.1145/502090.502097, arXiv:quant-ph/9802049] 2, 5, 25
[12] R ICHARD B EIGEL: The polynomial method in circuit complexity. In Proc. 8th IEEE Conf.
on Structure in Complexity Theory (SCT’93), pp. 82–95. IEEE Comp. Soc. Press, 1993.
[doi:10.1109/SCT.1993.336538] 2
[13] R ICHARD B EIGEL: Perceptrons, PP, and the polynomial hierarchy. Comput. Complexity, 4(4):339–
349, 1994. Preliminary version in SCT’92. [doi:10.1007/BF01263422] 2
[14] A LEKSANDRS B ELOVS AND A NSIS ROSMANIS: Adversary lower bounds for the collision and the
set equality problems, 2013. [arXiv:1310.5185] 5
[15] A LEKSANDRS B ELOVS AND ROBERT Š PALEK: Adversary lower bound for the k-sum problem. In
Proc. 4th Conf. on Innovations in Theoret. Comput. Sci. (ITCS’13), pp. 323–328. ACM Press, 2013.
[doi:10.1145/2422436.2422474, arXiv:1206.6528] 5
[16] A NDREJ B OGDANOV, Y UVAL I SHAI , E MANUELE V IOLA , AND C HRISTOPHER W ILLIAMSON:
Bounded indistinguishability and the complexity of recovering secrets. In Proc. of 36th Internat.
Cryptology Conf. (CRYPTO’16), volume 9816 of LNCS, pp. 593–618. Springer, 2016. Available at
ECCC. [doi:10.1007/978-3-662-53015-3_21] 4
[17] G ILLES B RASSARD , P ETER H ØYER , AND A LAIN TAPP: Quantum algorithm for the collision
problem. In Encyclopedia of Algorithms, pp. 1–99. Springer, 2008. Preliminary version in ACM
SIGACT News. [doi:10.1007/978-0-387-30162-4_304, arXiv:quant-ph/9705002] 2, 19, 25
[18] H ARRY B UHRMAN , N IKOLAI K. V ERESHCHAGIN , AND RONALD DE W OLF: On computation and
communication with small bias. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07),
pp. 24–32. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.18] 2, 5
[19] M ARK B UN AND J USTIN T HALER: Dual lower bounds for approximate degree and Markov-
Bernstein inequalities. Inform. and Comput., 243:2–25, 2015. Preliminary version in ICALP’13.
[doi:10.1016/j.ic.2014.12.003, arXiv:1302.6191] 2, 3, 9, 10, 11, 12, 14, 15, 26
[20] M ARK B UN AND J USTIN T HALER: Hardness amplification and the approximate degree of
constant-depth circuits. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming
(ICALP’15), volume 9134 of LNCS, pp. 268–280. Springer, 2015. [doi:10.1007/978-3-662-47672-
7_22, arXiv:1311.1616] 3, 4, 5, 12
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 30
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
[21] K ARTHEKEYAN C HANDRASEKARAN , J USTIN T HALER , J ONATHAN U LLMAN , AND A NDREW
WAN: Faster private release of marginals on small databases. In Proc. 5th Conf. on Innovations in
Theoret. Comput. Sci. (ITCS’14), pp. 387–402. ACM Press, 2014. [doi:10.1145/2554797.2554833,
arXiv:1304.3754] 2
[22] P ETER H ØYER , T ROY L EE , AND ROBERT S PALEK: Negative weights make adversaries stronger.
In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-
ph/0611054] 5
[23] P ETER H ØYER , M ICHELE M OSCA , AND RONALD DE W OLF: Quantum search on bounded-error
inputs. In Proc. 30th Internat. Colloq. on Automata, Languages and Programming (ICALP’03),
volume 2719 of LNCS, pp. 291–299. Springer, 2003. [doi:10.1007/3-540-45061-0_25, arXiv:quant-
ph/0304052] 3
[24] A DAM TAUMAN K ALAI , A DAM R. K LIVANS , Y ISHAY M ANSOUR , AND ROCCO A. S ERVEDIO:
Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. Preliminary version in
FOCS’05. [doi:10.1137/060649057] 2
[25] VARUN K ANADE AND J USTIN T HALER: Distribution-independent reliable learning. In Proc. 27th
Ann. Conf. on Learning Theory (COLT’14), pp. 3–24, 2014. JMLR. [arXiv:1402.5164] 2
1/3
[26] A DAM R. K LIVANS AND ROCCO A. S ERVEDIO: Learning DNF in time 2Õ(n ) . J. Comput. System
Sci., 68(2):303–318, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.007] 2
[27] A DAM R. K LIVANS AND ROCCO A. S ERVEDIO: Toward attribute efficient learning of decision lists
and parities. J. Machine Learning Res., 7:587–602, 2006. JMLR. Preliminary version in COLT’04.
2
[28] S AMUEL K UTIN: Quantum lower bound for the collision problem with small range. Theory of
Computing, 1(2):29–36, 2005. [doi:10.4086/toc.2005.v001a002] 2, 3, 4, 7, 9, 11, 12
[29] L OÏCK M AGNIN AND J ÉRÉMIE ROLAND: Explicit relation between all lower bound techniques
for quantum query complexity. Internat. J. Quantum Inform., 13(4):1350059, 2015. Preliminary
versions in STACS’13 and ECCC. [doi:10.1142/S0219749913500597, arXiv:1209.2713] 5
[30] N OAM N ISAN AND M ARIO S ZEGEDY: On the degree of boolean functions as real poly-
nomials. Comput. Complexity, 4(4):301–313, 1994. Preliminary version in STOC’92.
[doi:10.1007/BF01263419] 3, 9, 11
[31] RYAN O’D ONNELL AND ROCCO A. S ERVEDIO: New degree bounds for polynomial threshold func-
tions. Combinatorica, 30(3):327–358, 2010. Preliminary version in STOC’03. [doi:10.1007/s00493-
010-2173-3] 3, 12
[32] R AMAMOHAN PATURI: On the degree of polynomials that approximate symmetric boolean
functions (preliminary version). In Proc. 24th STOC, pp. 468–474. ACM Press, 1992.
[doi:10.1145/129712.129758] 10, 11
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 31
M ARK B UN AND J USTIN T HALER
[33] B EN W. R EICHARDT: Span programs and quantum query complexity: The general adversary bound
is nearly tight for every boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc.
Press, 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759] 5
[34] B EN W. R EICHARDT: Reflections for quantum query algorithms. In Proc. 22nd Ann.
ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011.
[doi:10.1137/1.9781611973082.44, arXiv:1005.1601] 5
[35] ROCCO A. S ERVEDIO , L I -YANG TAN , AND J USTIN T HALER: Attribute-efficient learning and
weight-degree tradeoffs for polynomial threshold functions. In Proc. 25th Ann. Conf. on Learning
Theory (COLT’12), volume 23, pp. 14.1–14.19, 2012. JMLR. 2
[36] A LEXANDER A. S HERSTOV: Communication lower bounds using dual polynomials. Bulletin of
the EATCS, 95:59–93, 2008. Available at EATCS. [arXiv:0805.2135] 2, 3
[37] A LEXANDER A. S HERSTOV: Separating AC0 from depth-2 majority circuits. SIAM J. Comput.,
38(6):2113–2129, 2009. Preliminary version in STOC’07. [doi:10.1137/08071421X] 2
[38] A LEXANDER A. S HERSTOV: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000,
2011. Preliminary version in STOC’08. [doi:10.1137/080733644, arXiv:0906.4291] 2, 3, 4, 5
[39] A LEXANDER A. S HERSTOV: Strong direct product theorems for quantum communication and
query complexity. SIAM J. Comput., 41(5):1122–1165, 2011. Preliminary version in STOC’11.
[doi:10.1137/110842661, arXiv:1011.4935] 3
[40] A LEXANDER A. S HERSTOV: Approximating the AND-OR tree. Theory of Computing, 9(20):653–
663, 2013. Preliminary version in ECCC. [doi:10.4086/toc.2013.v009a020] 3
[41] A LEXANDER A. S HERSTOV: The intersection of two halfspaces has high threshold degree.
SIAM J. Comput., 42(6):2329–2374, 2013. Preliminary versions in FOCS’09 and ECCC.
[doi:10.1137/100785260, arXiv:0910.1862] 2, 3, 26
[42] A LEXANDER A. S HERSTOV: Breaking the Minsky-Papert barrier for constant-depth cir-
cuits. In Proc. 46th STOC, pp. 223–232. ACM Press, 2014. Also available at ECCC.
[doi:10.1145/2591796.2591871] 3, 4, 5
[43] A LEXANDER A. S HERSTOV: The power of asymmetry in constant-depth circuits. In
Proc. 56th FOCS, pp. 431–450. IEEE Comp. Soc. Press, 2015. Also available at ECCC.
[doi:10.1109/FOCS.2015.34] 3, 4, 5
[44] YAOYUN S HI: Quantum lower bounds for the collision and the element distinctness problems. In
Proc. 43rd FOCS, pp. 513–519. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181975,
arXiv:quant-ph/0112086] 2, 3
[45] YAOYUN S HI AND Y UFAN Z HU: Quantum communication complexity of block-composed func-
tions. Quantum Inf. Comput., 9(5):444–460, 2009. ACM DL. [arXiv:0710.0095] 2
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 32
D UAL P OLYNOMIALS FOR C OLLISION AND E LEMENT D ISTINCTNESS
[46] ROBERT Š PALEK: A dual polynomial for OR, 2008. [arXiv:0803.4516] 3, 9, 14
[47] ROBERT Š PALEK AND M ARIO S ZEGEDY: All quantum adversary methods are equivalent. Theory
of Computing, 2(1):1–18, 2006. Preliminary version in ICALP’05. [doi:10.4086/toc.2006.v002a001]
5
[48] J USTIN T HALER: Lower bounds for the approximate degree of block-composed functions. Electron.
Colloq. on Comput. Complexity (ECCC), 21(150), 2014. ECCC. 3, 26
[49] J USTIN T HALER , J ONATHAN U LLMAN , AND S ALIL P. VADHAN: Faster algorithms for privately
releasing marginals. In Proc. 39th Internat. Colloq. on Automata, Languages and Programming
(ICALP’12), volume 7391 of LNCS, pp. 810–821. Springer, 2012. [doi:10.1007/978-3-642-31594-
7_68, arXiv:1205.1758] 2
[50] H ENRY Y UEN: A quantum lower bound for distinguishing random functions from random per-
mutations. Quantum Inf. Comput., 14(13-14):1089–1097, 2014. ACM DL. [arXiv:1310.2885]
5
[51] M ARK Z HANDRY: A note on the quantum collision and set equality problems. Quantum Inf.
Comput., 15(7-8):557–567, 2015. ACM DL. [arXiv:1312.1027] 5
[52] S HENGYU Z HANG: On the power of Ambainis lower bounds. Theoret. Comput. Sci., 339(2-
3):241–256, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.01.019, arXiv:quant-
ph/0311060] 5
AUTHORS
Mark Bun
Ph. D. Candidate
Harvard University, Cambridge, MA
mbun seas harvard edu
http://people.seas.harvard.edu/~mbun/
Justin Thaler
Research Scientist
Yahoo Research, New York, NY
jthaler fas harvard edu
http://people.seas.harvard.edu/~jthaler/
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 33
M ARK B UN AND J USTIN T HALER
ABOUT THE AUTHORS
M ARK B UN is a Ph. D. student in the Theory of Computation group at Harvard University,
where he is advised by Salil Vadhan. His research interests include computational
complexity, differential privacy, cryptozoology, and learning theory. As a native Seattleite,
he enjoys coffee, rain, composting, competitive paper airplane throwing, extreme ironing,
and wingsuit base jumping.
J USTIN T HALER is a Research Scientist at Yahoo Research in New York City. Previously,
Justin spent a year as a Research Fellow at the Simons Institute for the Theory of Comput-
ing. He received his Ph. D. in Computer Science from Harvard University in 2013 under
the supervision of Michael Mitzenmacher. His research interests include communication
complexity, computational learning theory, algorithms for massive datasets, and verifiable
computation. He enjoys running and binge watching Veronica Mars (not necessarily at
the same time), and his favorite norm is L∞ .
T HEORY OF C OMPUTING, Volume 12 (16), 2016, pp. 1–34 34