The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

1 Introduction Approximate degree. The approximate degree of a Boolean function f : {-1, 1} n → {-1, 1}, denoted deg( f ), is the least degree of a real polynomial p such that |p(x)f (x)| ≤ 1/3 for all x ∈ {-1, 1} n . Approximate degree is a basic measure of the complexity of a Boolean function, and has diverse applications throughout theoretical computer science.

Upper bounds on approximate degree are at the heart of the most powerful known learning algorithms in a number of models [10,46,47,49,50,63,68], algorithmic approximations for the inclusion-exclusion principle [45,70], and algorithms for differentially private data release [35,87]. A recent line of work [84,85] has used approximate degree upper bounds to show new lower bounds on the formula and graph complexities of explicit functions.

Lower bounds on approximate degree have enabled progress in several areas of complexity theory, including communication complexity [27,36,38,39,41,64,69,72,74,77], circuit complexity [60,71], oracle separations [15,21], and secret-sharing [20]. Most importantly for this paper, approximate degree lower bounds have been critical in shaping our understanding of quantum query complexity [1,3,13],

In spite of the importance of approximate degree, major gaps remain in our knowledge. In particular, the approximate degrees of many basic functions are still unknown. Our goal in this paper is to determine the approximate degrees of several natural functions for which there were significant gaps between known upper and lower bounds.

Quantum query complexity. While determining the approximate degree of basic functions of interest is a test of our understanding of approximate degree, it is also motivated by the study of quantum algorithms. In the quantum query model, a quantum algorithm is given query access to the bits of an input x, and the goal is to compute some function f of x while minimizing the number of queried bits. Quantum query complexity captures much of the power of quantum computing, and most quantum algorithms were discovered in or can easily be described in the query setting.

Approximate degree was one of the first general lower bound techniques for quantum query complexity. In 1998, Beals et al. [13] observed that the bounded-error quantum query complexity of a function f is lower bounded by (one half times) the approximate degree of f . Since polynomials are sometimes easier to understand than quantum algorithms, this observation led to a number of new lower bounds on quantum query complexity. This method of proving quantum query lower bounds is called the polynomial method.

After several significant quantum query lower bounds were proved via the polynomial method (including the work of Aaronson and Shi [3], who proved optimal lower bounds for the collision and element distinctness problems), the polynomial method took a back seat. Since then, the positive-weights adversary method [5,12,52,92] and the newer negative-weights adversary method [44,55,66] have become the tools of choice for proving quantum query lower bounds (with some notable exceptions, such as Zhandry's recent tight lower bound for the set equality problem [91]). This leads us to our second goal for this work.

In this article, we seek to resolve several open problems in quantum query complexity using approximate degree as the lower bound technique. A distinct advantage of proving quantum query lower bounds with the polynomial method is that any such bound can be "lifted" via Sherstov's pattern matrix method [72] to a quantum communication lower bound (even with unlimited shared entanglement [56]); THEORY OF COMPUTING, Volume 16 (10), 2020, pp. Best prior upper bound Our lower bound Best prior lower bound k-Distinctness O(n 3/4-1/(2 k+2 -4) ) [16] Ω(n 3/4-1/(2k) ) Ω(n 2/3 ) [3] Image size testing

Table 1: Our lower bounds on quantum query complexity and approximate degree vs. prior work. such a result is not known for any other quantum query lower bound technique. More generally, using approximate degree as a lower bound technique for quantum query complexity has other advantages, such as the ability to show lower bounds for zero-error and small-error quantum algorithms [24], unbounded-error quantum algorithms [13], and time-space tradeoffs [48].

Quantum query complexity and approximate degree. We illustrate the power of the polynomial method by proving optimal or nearly optimal bounds on several functions studied in the quantum computing literature. These results are summarized in Table 1, and definitions of the problems considered can be found in Section 1.1. Since the upper bounds for these functions were shown using quantum algorithms, our results determine both the quantum query complexity and approximate degree of these functions.

For most of the functions studied in this paper, the positive-weights adversary bound provably cannot show optimal lower bounds due to the certificate complexity barrier [83,92] and the property testing barrier [44]. While these barriers do not apply to the negative-weights variant (which is actually capable of proving tight quantum query lower bounds for all functions [55,66]), the negative-weights adversary method is often challenging to apply to specific problems, and tight bounds for the problems we consider have remained unknown for a long time.

For the functions presented in Table 1, the approximate degree and quantum query complexity are essentially the same. This is not the case for the surjectivity function, which has played an important role in the literature on approximate degree and quantum query complexity. Specifically, Beame and Machmouchi [14] showed that surjectivity has quantum query complexity Θ(n). On the other hand, Sherstov recently showed that surjectivity has approximate degree Õ(n 3/4 ) [78]. Surjectivity is the only known example of a "natural" function separating approximate degree from quantum query complexity; prior examples of such functions [2,7] were contrived, and (unlike surjectivity) specifically constructed to separate the two measures.

Our final result gives a nearly tight estimate of the approximate degree of surjectivity. We prove a new lower bound of Ω(n 3/4 ), which matches Sherstov's upper bound up to logarithmic factors. We also give a new construction of an approximating polynomial of degree Õ(n 3/4 ), using very different techniques than [78]. We believe that our proof of this Õ(n 3/4 ) upper bound is of independent interest. In particular, our lower bound proof for surjectivity is specifically tailored to showing optimality of our upper bound construction, in a sense that can be made formal via complementary slackness. We are optimistic that our THEORY OF COMPUTING, Volume 16 (10), 2020, pp. Prior upper bound Our upper bound Our lower bound Prior lower bound Surjectivity Õ(n 3/4 ) [78] Õ(n 3/4 ) Ω(n 3/4 ) Ω(n 2/3 ) [3] Table 2: Our bounds on the approximate degree of surjectivity vs. prior work. approximation techniques will be useful for showing additional tight approximate-degree bounds in the future.

Functions considered

We now informally describe the functions studied in this paper. These functions are formally defined in Section 2.4. Let R be a power of two and N ≥ R, and let n = N • log 2 R. Most of the functions that we consider interpret their inputs in {-1, 1} n as a list of N numbers from a range [R], and determine whether this list satisfies various natural conditions. We let the frequency f i of range item i ∈ R denote the number of times i appears in the input list.

In this paper we study the following functions in which the input is N numbers from a range [R]:

• Surjectivity (SURJ): Do all range items appear at least once?

• k-Distinctness: Is there a range item that appears k or more times?

• Image size testing: Decide if all range items appear at least once or if at most γ • R range items appear at least once, under the promise that one of these is true. • Statistical distance from uniform (SDU): Interpret the input as a probability distribution p, where p i = f i /N. Compute the statistical distance of p from the uniform distribution over R up to some small additive error ε. • Shannon entropy: Interpret the input as a probability distribution p, where p i = f i /N. Compute the Shannon entropy ∑ i∈R p i • log(1/p i ) of p up to additive error ε.

An additional function we consider that does not fit neatly into the framework above is k-junta testing.

• k-Junta testing: Given an input in {-1, 1} n representing the truth table of a function {-1, 1} log n → {-1, 1}, determine whether this function depends on at most k of its input bits, or is at least ε-far from any such function.

We give tight or nearly tight bounds on the quantum query complexities and/or approximate degrees of all of the functions above. Our lower bounds for SURJ, k-distinctness, image size testing, SDU, and entropy approximation all require N to be "sufficiently larger" than R, by a certain constant factor. For simplicity, throughout this introduction we do not make this requirement explicit, and for this reason we label the theorems in this introduction informal.

Results in detail

Surjectivity. In the surjectivity problem we are given N numbers from [R] and must decide if every range item appears at least once in the input.

The quantum query complexity of this problem was studied by Beame and Machmouchi [14], who proved a lower bound of Ω(n), which was later improved by Sherstov to the optimal Θ(n) [80]. Beame and Machmouchi [14] explicitly leave open the question of determining the approximate degree of surjectivity. Recently, Sherstov [78] showed an upper bound of Õ(n 3/4 ) on the approximate degree of this function. The best prior lower bound was Ω(n 2/3 ) [3,33].

We give a completely different construction of an approximating polynomial for surjectivity with degree Õ(n 3/4 ). We also prove a matching lower bound, which shows that the approximate degree of the surjectivity function is Θ(n 3/4 ).

Theorem 1.1 (Informal). The approximate degree of SURJ is Θ(n 3/4 ). k-Distinctness. In this problem, we are given N numbers in [R] and must decide if any range item appears at least k times in the list (i. e., is there an i ∈ [R] with f i ≥ k?). This generalizes the well-studied element distinctness problem, which is the same as 2-distinctness.

Ambainis [8] first used quantum walks to give an O(n k/(k+1) ) upper bound on the quantum query complexity of any problem with certificates of size k, including k-distinctness and k-sum. 1 Later, Belovs introduced a beautiful new framework for designing quantum algorithms [17] and used it to improve the upper bound for k-distinctness to O(n 3/4-1/(2 k+2 -4) ) [16]. Several subsequent works have used Belovs' k-distinctness algorithm as a black-box subroutine for solving more complicated problems (e. g., [58,61]).

As for lower bounds, Aaronson and Shi [3] established an Ω(n 2/3 ) lower bound on the approximate degree of k-distinctness for any k ≥ 2. Belovs and Špalek used the adversary method to prove a lower bound of Ω(n k/(k+1) ) on the quantum query complexity of k-sum, showing that Ambainis' algorithm is tight for k-sum. They asked whether their techniques can prove an ω(n 2/3 ) quantum query lower bound for k-distinctness. We achieve this goal, but using the polynomial method instead of the adversary method. Our main result is the following: Theorem 1.2 (Informal). For any k ≥ 2, the approximate degree and quantum query complexity of k-distinctness is Ω(n 3/4-1/(2k) ). This is nearly tight for large k, as it approaches Belovs' upper bound of O(n 3/4-1/(2 k+2 -4) ). Note that the exponent in both bounds approaches 3/4. It remains an intriguing open question to close the gap between n 3/4-1/(2 k+2 -4) and n 3/4-1/(2k) , especially for small values of k ≥ 3.

Our k-distinctness lower bound also implies an Ω(n 3/4-1/(2k) ) lower bound on the quantum query complexity of approximating the maximum frequency, F ∞ , of any element up to relative error less than 1/k [61], improving over the previous best bound of Ω(n 2/3 ).

Image size testing. In this problem, we are given N numbers in [R] and 0 < γ < 1, and must decide if every range item appears at least once or if at most γ • R range items appear at least once. We show for any γ > 0, the problem has approximate degree and quantum query complexity Ω( √ n). This holds as long as N = c • R for a certain constant c > 0.

Theorem 1.3 (Informal). The approximate degree and quantum query complexity of image size testing is

This lower bound is tight, matching a quantum algorithm of Ambainis, Belovs, Regev, and de Wolf [9], and confirms a conjecture from their work. The previous best lower bound was Ω(n 1/3 ) [9] obtained via reduction to the collision lower bound [3]. The classical query complexity of this problem is Θ(n/ log n) [89].

The version of image size testing we define is actually a special case of the one studied in [9]. The version we define is solvable via the following simple algorithm making O( √ n) queries: pick a random range item, and Grover search for an instance of that range item. The fact that our lower bound holds even for this special case of the problem considered in prior work obviously only makes our lower bound stronger.

This lower bound also serves as a starting point to establish the next three lower bounds.

k-Junta testing. In this problem, we are given the truth table of a Boolean function and have to determine if the function depends on at most k variables or if it is ε-far from any such function.

The best classical algorithm for this problem uses O(k log k + k/ε) queries [19]. The problem was first studied in the quantum setting by Atıcı and Servedio [11], who gave a quantum algorithm making O(k/ε) queries. This was later improved by Ambainis et al. [9] to Õ( k/ε). They also proved a lower bound of Ω(k 1/3 ). Via a connection established by Ambainis et al., our image size testing lower bound implies a Ω( √ k) lower bound on the approximate degree and quantum query complexity of k-junta testing (for some ε = Ω(1)).

Theorem 1.4 (Informal). The approximate degree and quantum query complexity of k-junta testing is

This matches the upper bound of [9], resolving the main open question from their paper.

Prior work on lower bounds for approximate degree

A relatively new lower-bound technique for approximate degree called the method of dual polynomials plays an essential role in our paper. This method of dual polynomials dates back to work of Sherstov [75] and Špalek [82], though dual polynomials had been used earlier to resolve longstanding questions in communication complexity [36,57,71,72,81]. To prove a lower bound for a function f via this method, one exhibits an explicit dual polynomial for f , which is a dual solution to a certain linear program capturing the approximate degree of f . A notable feature of the method of dual polynomials is that it is lossless, in the sense that it can exhibit a tight lower bound on the approximate degree of any function f (though actually applying the method to specific functions may be highly challenging). Prior to the method of dual polynomials, the primary tool available for proving approximate degree lower bounds was symmetrization, introduced by Minsky and Papert [60] in the 1960s. Although powerful, symmetrization is not a lossless technique.

Most prior work on the method of dual polynomials can be understood as establishing hardness amplification results. Such results show how to take a function f that is "somewhat hard" to approximate by low-degree polynomials, and turn f into a related function g that is much harder to approximate. Here, harder means either that g requires larger degree to approximate to the same error as f , or that approximations to g of a given degree incur much larger error than do approximations to f of the same degree.

Results for block-composed functions. Until very recently, the method of dual polynomials had been used exclusively to prove hardness amplification results for block-composed functions. That is, the harder function g would be obtained by block-composing f with another function h, i. e., g = h • f . Here, a function g :

its input as a sequence of n blocks, applies f to each block, and then feeds the n outputs into h.

The method of dual polynomials turns out to be particularly suited to analyzing block-composed functions, as there are sophisticated ways of "combining" dual witnesses for h and f individually to give an effective dual witness for h • f [21,29,30,73,75,[79][80][81]86]. Prior work on analyzing block-composed functions has, for example, resulted in the determination of the approximate degree of the function f (x) = n i=1 m j=1 x i j , known as the AND-OR tree, which had been open for 19 years [29,73], established new lower bounds for AC 0 under basic complexity measures including discrepancy [30,79,80,86], THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71 sign-rank [32], and threshold degree [79,80], and resolved a number of open questions about the power of statistical zero knowledge proofs [21].

Beyond block-composed functions. While the aforementioned results led to considerable progress in complexity theory, many basic questions require understanding the approximate degree of non-blockcomposed functions. One prominent example with many applications is to exhibit an AC 0 circuit over n variables with approximate degree Ω(n). Until very recently, the best result in this direction was Aaronson and Shi's well-known Ω(n 2/3 ) lower bound on the approximate degree of the element distinctness function (which is equivalent to k-distinctness for k = 2) [3]. However, Bun and Thaler [33] recently achieved a near-resolution of this problem by proving the following theorem.

Theorem 1.7 (Bun and Thaler [33]). For any constant δ > 0, there is an AC 0 circuit with approximate degree Ω(n 1-δ ).

The reason that Theorem 1.7 required moving beyond block-composed functions is the following result of Sherstov [76].

Theorem 1.8 (Sherstov). For any Boolean functions f and h, deg(h

Theorem 1.8 implies that the approximate degree of h • f (viewed as a function of its input size) is never higher than the approximate degree of f or h individually (viewed as a function of their input sizes). For example, if f and h are both functions on n inputs, and both have approximate degree O(n 1/2 ), then h • f has N := n 2 inputs, and by Theorem 1.8, deg(h

This means that block-composing multiple AC 0 functions does not result in a function of higher approximate degree (as a function of its input size) than that of the individual functions. Bun and Thaler [33] overcome this hurdle by introducing a way of analyzing functions that cannot be written as a block-composition of simpler functions.

Bun and Thaler's techniques set the stage to finding the approximate degrees of many basic functions using the method of dual polynomials. However, they were not refined enough to accomplish this on their own. Our lower bounds in this paper are obtained by refining and extending the methods of [33].

Our techniques

In order to describe our techniques, it is helpful to explain the process by which we discovered the tight Θ(n 3/4 ) lower and upper bounds for surjectivity (cf. Theorem 1.1). It has previously been observed [29,33,86] that optimal dual polynomials for a function f tend to be tailored (in a sense that can be made precise via complementary slackness) to showing optimality of some specific approximation technique for f . Hence, constructing a dual polynomial for f can provide a strong hint as to how to construct an optimal approximation for f , and vice versa.

Upper bound for surjectivity. In [33], Bun and Thaler constructed a dual polynomial witnessing a suboptimal bound of Ω(nfoot_3/foot_4 ) for SURJ. Even though this dual polynomial is suboptimal, it still provided a major clue as to what an optimal approximation for SURJ should look like: it curiously ignored all inputs failing to satisfy the following condition. Condition 1.9. Every range item has frequency at most T , for a specific threshold T = O(N 1/3 ) N.

This suggested that an optimal approximation for SURJ should treat inputs satisfying Condition 1.9 differently than other inputs, leading us to the following multi-phase construction (for clarity and brevity, this overview is simplified). The first phase constructs a polynomial p of degree O(n 3/4 ) approximating SURJ on all inputs satisfying Condition 1.9. However, p may be exponentially large on other inputs. The second phase constructs a polynomial q of degree O(n 3/4 ) that is exponentially small on inputs x that do not satisfy Condition 1.9 (in particular, q(x) 1/p(x) for such x), and is close to 1 otherwise. The product p • q still approximates SURJ on inputs satisfying Condition 1.9, and is exponentially small on all other inputs. Notice that deg(p • q) ≤ deg(p) + deg(q) = O(n 3/4 ). Combining the above with an additional averaging step (the details of which we omit from this introduction) yields an approximation to SURJ that is accurate on all inputs.

Lower bound for surjectivity. With the O(n 3/4 ) upper bound in hand, we were able to identify the fundamental bottleneck preventing further improvement of the upper bound. This suggested a way to refine the techniques of [33] to prove a matching lower bound. Once the tight lower bound for SURJ was established, we were able to identify additional refinements to analyze the other functions that we consider. We now describe this in more detail.

Bun and Thaler's [33] (suboptimal) lower bound analysis for SURJ proceeds in two stages. In the first stage, proving a lower bound for SURJ (on N input list items and R range items) is reduced to the problem of proving a lower bound for the block-composed function AND R • OR N , 2 under the promise that the input has Hamming weight at most N. 3 In this paper, we use this stage of their analysis unmodified.

The second stage proves an Ω(R 2/3 ) lower bound for the latter problem by leveraging much of the machinery developed to analyze the approximate degree of block-composed functions [29,65,73]. To describe this machinery, we require the following notion. A dual polynomial that witnesses the fact that deg ε ( f n ) ≥ d is a function ψ : {-1, 1} n → [-1, 1] satisfying the following three conditions.

If ψ satisfies this condition, it is said to be well correlated with f .

• For all polynomials p : {-1, 1} n → R of degree less than d, we have ∑ x∈{-1,1} n p(x) • ψ(x) = 0. If ψ satisfies this condition, it is said to have pure high degree at least d.

In more detail, the second stage of the analysis from [33] itself proceeds in two steps. First, the authors consider a dual witness ψ for the high approximate degree of AND R • OR N that was constructed in prior work [29]. ψ is constructed by taking dual witnesses φ and γ for the high approximate degrees of AND R and OR N individually, and "combining" them in a specific way [54,75,81] to obtain a dual witness for the high approximate degree of their block composition AND R • OR N .

Unfortunately, ψ only witnesses a lower bound for AND R • OR N without the promise that the Hamming weight of the input is at most N. To address this issue, it is enough to "post-process" ψ so that it no longer "exploits" any inputs of Hamming weight larger than N (formally, ψ(x) should equal zero for any inputs in {-1, 1} R•N of Hamming weight more than N). The authors accomplish this by observing that ψ "almost ignores" all such inputs (i. e., it places exponentially little total mass on all such inputs), and hence it is possible to perturb ψ to make it completely ignore all such inputs.

Key to this step is the fact that the "inner" dual witness γ for the high approximate degree of the OR N function satisfies a "Hamming weight decay" condition:

for a suitable polynomial function.

To improve the lower bound for SURJ from Ω(n 2/3 ) to the optimal Ω(n 3/foot_5 ), we observe that γ in fact satisfies a much stronger decay condition: while the inverse-polynomial decay property of Equation (1.1) is tight for small Hamming weights |x|, |γ(x)| actually decays exponentially quickly once |x| is larger than a certain threshold t. This observation is enough to obtain the tight Ω(n 3/4 ) lower bound for SURJ.

For intuition, it is worth mentioning that a primal formulation of the dual decay condition that we exploit shows that any low-degree polynomial p that is an accurate approximation to OR N on low Hamming-weight inputs requires large degree, even if |p(x)| is allowed to be exponentially large for inputs of Hamming weight more than t. 4 This is precisely the bottleneck that prevents us from improving our upper bound for SURJ to o(N 3/4 ). In this sense, our dual witness is intuitively tailored to showing optimality of the techniques used in our upper bound.

Other lower bounds. To obtain the lower bound for k-distinctness, the first stage of the analysis of [33] reduces to a question about the approximate degree of the block-composed function OR R • THR k N , under the promise that the input has Hamming weight at most N. Here THR k N : {-1, 1} N → {-1, 1} denotes the function that evaluates to -1 if and only if the Hamming weight of its input is at least k. By constructing a suitable dual witness for THR k N , and combining it with a dual witness for OR N via similar techniques as in our construction for SURJ, we are able to prove our Ω(n 3/4-1/(2k) ) lower bound for k-distinctness. (This description glosses over several significant technical issues that must be dealt with to ensure that the combined dual witness is well-correlated with OR R • THR k N ). 5Recall that our lower bounds for k-junta testing, SDU, and entropy approximation are derived as consequences of our lower bound for image size testing. The connection between image size testing and junta testing was established by Ambainis et al. [9]. The reason that the image testing lower bound implies lower bounds for SDU is the following. Consider any distribution p over [R] such that all probabilities p i are integer multiples of 1/N for some N = O(R). Then if p has full support, p is guaranteed to be somewhat close to uniform, while if p has small support, p must be very far from uniform. We obtain our lower bound for entropy approximation using a simple reduction from SDU due to Vadhan [88].

To obtain our lower bound for image size testing, we observe that the first stage of the analysis of [33] reduces to a question about the approximate degree of the block-composed function GapAND R • OR N , under the promise that the input has Hamming weight at most N. Here, GapAND R is the promise function that outputs -1 if all of its inputs equal -1, outputs +1 if fewer than γ • R of its inputs are -1, and is undefined otherwise.

Roughly speaking, we obtain the desired Ω(n 1/2 ) lower bound by combining a dual witness for GapAND R • OR N from prior work [30] with the same techniques as in our construction for SURJ. However, additional technical refinements to the analysis of [33] are required to obtain our results. In particular, the analysis of [33] only provides a lower bound for SURJ if N = Ω(R • log 2 (R)). But in order to infer our lower bound for SDU and entropy approximation (as well as k-junta testing for ε = Ω(1)), it is essential that the lower bound hold for N = O(R). This is because a distribution with full support is guaranteed to be Ω(1)-close to uniform if all probabilities are integer multiples of 1/N with N = O(R), but this is not the case otherwise. (Consider, e. g., a distribution that places mass 1 -1/ log 2 (R) on a single range item, and spreads out the remaining mass evenly over all other range items). Refining the methods of [33] to yield lower bounds even when N = O(R) requires a significantly more delicate analysis than in [33].

A diagram indicating how we obtain our results and the relationships that we establish between problems is given in Figure 1.

Surjectivity

Definition 2.8.

there exists an i such that s i = j.

When N and R are clear from context, we will often refer to the function SURJ without the explicit dependence on these parameters. It will sometimes be convenient to think of the input to SURJ N,R as a function mapping {-1, 1} n → {-1, 1} rather than [R] N → {-1, 1}. When needed, we assume that R is a power of 2 and an element of [R] is encoded in binary using log R bits. In this case we will view surjectivity as a function on n = N log R bits, i. e., SURJ : {-1, 1} n → {-1, 1}.

For technical reasons, when proving lower bounds, it will be more convenient to work with a variant of SURJ where the range [R] is augmented by a "dummy element" 0 that is simply ignored by the function. That is, while any of the items s 1 , . . . , s N may take the dummy value 0, the presence of a 0 in the input is not required for the input to be deemed surjective. We denote this variant of surjectivity by dSURJ. More formally:

there exists an i such that s i = j.

The following simple reduction shows that a lower bound on the approximate degree of dSURJ implies a lower bound for SURJ itself.

Proposition 2.10. Let ε > 0 and N ≥ R. Then

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71 Proof. Let p : {-1, 1} (N+1)•log(R+1) → {-1, 1} be a polynomial of degree d that ε-approximates SURJ N+1,R+1 . We will use p to construct a polynomial of degree d that ε-approximates dSURJ N,R . Recall that an input to dSURJ N,R takes the form (s 1 , . . . , s N ) where each s i is the binary representation of a number in [R] 0 . Define the transformation T :

Note that as a mapping between binary representations, the function T is exactly computed by a vector of polynomials of degree at most log(R + 1). For every

Hence, the polynomial p(T (s 1 ), . . . ,

As with surjectivity, it will be convenient to work with a variant of k-distinctness where [R] is augmented with a dummy item: Definition 2.12. For integers k, N, R with k ≤ N, define the function

For k ≥ 2, a lower bound on the approximate degree of dDIST k implies a lower bound on the approximate degree of DIST k . The restriction that k ≥ 2 is essential, because the function DIST 1 is the constant function that evaluates to TRUE on any input (since at least one range item must always have frequency at least one), whereas dDIST 1 contains OR N as a subfunction, and hence has approximate degree at least Ω( √ N).

Proposition 2.13. Let ε > 0, N, R ∈ N, and k ≥ 2. Then

Proof. The proof is similar to that of Proposition 2.10, but uses a slightly more involved reduction. Let p : {-1, 1} 2N•log(R+N) → R be a polynomial of degree d that ε-approximates DIST k N,R+N . We will use p to construct a polynomial of degree d that ε-approximates

As a mapping between binary representations, the function T = (T 1 , . . . , T N ) is exactly computed by a vector of polynomials of degree at most log(R + 1). For every (s 1 , . . . , s N ) ∈ [R] N 0 , observe that

Hence, the polynomial p(T (s 1 ), . . . , T (s N ))

is a polynomial of degree d • log(R + 1) that ε-approximates dSURJ N,R .

Connecting symmetric properties and block-composed functions

An important ingredient in [33] is the relationship between the approximate degree of a property of a list of numbers (such as SURJ) and the approximate degree of a simpler block-composed function, defined as follows.

Definition 2.14. For functions f :

Suppose g is a symmetric function, in the sense that for any x ∈ {-1, 1} N and any permutation σ :

Equivalently, the value of g on any input x depends only on its Hamming weight |x|.

The functions f and g give rise to two functions. The first, which we denote by

The second, which we denote by

, is the block composition of f and g restricted to inputs of Hamming weight at most N. Formally, these functions are defined as

The following proposition from [33], which in turn relies heavily on a clever symmetrization argument due to due to Ambainis [6], relates the approximate degrees of the two functions F prop and F ≤N . Theorem 2.15. Let f : {-1, 1} R → {-1, 1} be any function and let g : {-1, 1} N → {-1, 1} be a symmetric function. Then for F prop and F ≤N defined above, and for any ε > 0, we have

In the case where f = AND R and g = OR N , the function F prop (s 1 , . . . , s N ) is the surjectivity function augmented with a dummy item, dSURJ N,R (s 1 , . . . , s N ). Hence, Corollary 2.16. Let N, R ∈ N. Then for any ε > 0,

Definition 2.17. For integers k, N with k ≤ N, define the function

where G ≤N :

A refinement of a technical lemma from prior work

The following technical proposition refines techniques of Bun and Thaler [33]. This proposition is useful for "zeroing out" the mass that a dual polynomial ξ places on inputs of high Hamming weight, if ξ is obtained via the dual-block method.

Definition 2.21. Let M ∈ N and α, β > 0. A function ω :

)

(2.13) Proposition 2.22. Let R ∈ N be sufficiently large, and let Φ :

)

The key refinement of Proposition 2.22 relative to the analysis of Bun and Thaler is that Proposition 2.22 applies when N = Θ(R) (assuming α = O(1)). In contrast, the techniques of Bun and Thaler required N = Ω(R • log 2 R). As indicated in Section 1.3, this refinement will be essential in obtaining our lower bounds for SDU, entropy approximation, and junta testing for constant proximity parameter.

The proof of Proposition 2.22 occurs in two steps. First, in Proposition 2.23, we show that ξ = Φ ψ places an exponentially small amount of mass on inputs outside of H N•R ≤N . Second, in Proposition 2.25, we construct a correction object ν that zeroes out the mass ξ places outside of H N•R ≤N without decreasing its pure high degree. Combining ξ with ν yields the desired object ζ .

(2.20)

By the definition of dual block composition, we have

Consequently,

Observe that for any

we may rewrite Expression (2.21) as

To control this quantity, we appeal to the following combinatorial lemma, whose proof we delay to Section 2.7.1 (this lemma is a substantial refinement of [33,Lemma 32]).

, and let R be sufficiently large. Let N = 20

be a sequence of non-negative functions where for every i,

(2.23)

where ∆ ≥ β √ αR/(4 ln 2 R).

Observe that the functions ω z i satisfy Condition (2.22) (cf. Equation (2.20)) and Condition (2.23) (cf. Property (2.13)). We complete the proof by bounding

Here, the equality appeals to the condition that Φ 1 = 1.

Our final dual witness ζ is obtained by modifying ξ = Φ ψ to zero out all of the mass it places on inputs of total Hamming weight larger than N. The following proposition gives sufficient conditions under which this postprocessing step can be done. Proposition 2.25 ( [33, Proposition 34], building on [65]). Let N ≥ R > D and let ξ :

Then there exists a function ν :

Remark 2.26. Proposition 2.25 is framed exclusively in the language of dual polynomials: it states that if a dual polynomial ξ places very little mass on inputs of Hamming weight more than N, then there exists another dual polynomial ν with certain useful properties (we ultimately use ν to zero out the mass that ξ places on inputs of Hamming weight more than N). Proposition 2.25 also has a clean primal formulation. Roughly speaking, it is equivalent to a bound on the growth rate of any polynomial of degree at most D that is bounded at all inputs of Hamming weight at most D. We direct the interested reader to [90] for details of this primal formulation.

We are now ready to combine Proposition 2.23 and Proposition 2.25 to complete the proof of Proposition 2.22.

Proof of Proposition 2.22. Let ξ = Φ ψ. By Proposition 2.23, we have

where ∆ ≥ β √ αR/(4 ln 2 R). By Proposition 2.25, there exists a function ν :

)

(2.26)

Observe that ξν 1 > 0, as ξ 1 = 1 (cf. Equation (2.8)) and ν 1 ≤ 1/10 (cf. Inequality (2.25)). Define the function

Since ν(x) = ξ (x) whenever |x| > N (cf. Equation (2.26)), the function ζ is supported on the set H N•R ≤N , establishing (2.18). We establish (2.16) by computing

Equation (2.17) is immediate from the definition of ζ . Finally, (2.15) follows from (2.14), (2.24), and linearity.

Proof of Lemma 2.24

Our final task is to prove Lemma 2.24, restated here for the reader's convenience.

be a sequence of non-negative functions where for every i,

(2.23)

where

Proof. Using the fact that the function 1/ √ t is decreasing, we may estimate

Proof. Let T = N 2M . For each s ∈ {T, . . . , R}, let

We begin with a simple, but important, structural observation about the set P.

Then we claim that there exists an s ∈ {T . . . , R} such that t i ≥ C(s) for at least s indices i ∈ [R]. To see this, assume without loss of generality that the entries of t are sorted so that t 1 ≥ t 2 ≥ • • • ≥ t R . Then there must exist an s ≥ T such that t s ≥ C(s). Otherwise, because no t i can exceed M, we would have:

where the last inequality follows from Lemma 2.29 and the fact that ∑ m s=1 s -1 ≤ ln m + 1 (and R is sufficiently large). Since the entries of t are sorted, the preceding values t 1 , . . . ,t s-1 ≥ C(s) as well.

For each subset S ⊆ [R], define

The observations above guarantee that for every t = (t 1 , . . . ,t R ) ∈ P, there exists some set S of size at least s ∈ {T, . . . , R} such that t i ≥ C(s) for all i ∈ S. Hence

s by Properties (2.22) and (2.23)

by Lemma 2.27

by Lemma 2.28

where

holds for sufficiently large R by the restrictions placed on α and β in the statement of the lemma.

Warmup: Approximating NOR

To convey the intuition behind our polynomial construction for surjectivity, we start by considering a much simpler function as an illustrative example. Consider the negation of the OR function on n bits, NOR : {0, 1} n → {0, 1}. We will give a novel construction of an approximating polynomial for NOR of degree Õ( √ n). Of course, this is not terribly interesting since it is already known that deg(NOR) = Θ( √ n) (cf. Lemma 2.6). But this construction highlights the main idea behind the more involved constructions to follow.

In many models of computation, such as deterministic or randomized query complexity, the NOR function remains just as hard if we restrict to inputs with |x| = 0 or |x| = 1 (where |x| denotes the Hamming weight of x ∈ {0, 1} n ). This is fairly intuitive, since distinguishing these two types of inputs essentially requires finding a single 1 among n possible locations. The fact that these inputs represent the "hard case" is true for approximate degree as well: any polynomial that uniformly approximates NOR to error 1/3 on Hamming weights 0 and 1, and merely remains bounded in [0, 1] on the rest of the hypercube, has degree Ω( √ n) [62].

However, if we remove the boundedness constraint on inputs of Hamming weight larger than 1, then there is a polynomial of degree one that exactly equals the NOR function on inputs of Hamming weight 0 and 1, namely, the polynomial 1 -∑ i x i . That is, if we view NOR as a promise function mapping H n ≤1 to {-1, 1}, then its approximate degree is Θ(n 1/2 ), but its unbounded approximate degree is just 1.

More generally, suppose that we only want the polynomial to approximate the NOR function on all inputs of Hamming weight up to T ≤ n, and we place no restrictions on the polynomial when evaluated at inputs of Hamming weight larger than T . This can be achieved by a polynomial of degree O( √ T ) (see Lemma 3.3 for a proof).

Let us refer to the set of low Hamming-weight inputs as P, i. e.,

The above discussion shows that we can construct a polynomial p of degree O( √ T ) that tightly approximates NOR on inputs x ∈ P, though |p(x)| may be exponentially large for x / ∈ P. On the other hand, distinguishing inputs with |x| = 0 from inputs with x / ∈ P also seems "easy". For example, a randomized algorithm that simply samples Θ(n/T ) bits and declares |x| = 0 if and only if it does not see a 1 is correct with high probability. Analogously, we can construct a low-degree polynomial q which distinguishes between |x| = 0 or x / ∈ P (and is bounded in [0, 1] for all inputs in {0, 1} n ): it is not hard to show (via an explicit construction involving Chebyshev polynomials, or by appeal to a quantum algorithm called quantum counting [22]) that there exists a polynomial q of degree O( n/T ) that accomplishes this.

To summarize the above discussion, we can construct polynomials p and q, of degree O( √ T ) and O( n/T ), respectively, with the following properties.

Now consider the polynomial p(x) • q(x). This polynomial approximates NOR on |x| = 0, since its value is in [0.81, 1]. It also approximates NOR on 1 ≤ |x| ≤ T , since its value is in [0, 1/10]. However, when x / ∈ P, although q(x) is small, we cannot ensure that the product p(x) • q(x) is small, since we have no control over p(x) for such x.

To fix this, we will construct a new polynomial q that behaves like q for x ∈ P and is extremely small when x / ∈ P (in particular 0 ≤ q(x) 1/|p(x)| for such x). To understand how small we need q to be, we need to determine just how large p(x) can be on inputs with x / ∈ P. To understand the behavior of p(x) outside of P, we can either analyze the behavior of an explicit polynomial of our choice for the NOR function or we can appeal to a general result about the growth of polynomials that are bounded in a region (see Lemma 3.3). In either case, we get that there exists an upper bound M = exp(O( √ T log n)) such that for all x / ∈ P, |p(x)| ≤ M. This leads us to design a new polynomial q, which has the same behavior as q for all x ∈ P, but is at most 1/(3M) when x / ∈ P. We can construct the polynomial q from q by applying standard error reduction to reduce the approximation error of q to ε = 1/(3M), which increases the degree by a multiplicative factor of O(log

In summary, we have now constructed polynomials p and q with the following behavior:

Caricatures of these polynomials are depicted in Figure 2 and Figure 3. It is now easy to see that the product r(x) = p(x) • q(x) is a (1/3)-error approximation to NOR for all x ∈ {0, 1} n . The degree of the constructed polynomial is deg(r)

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71

Figure 2: Caricature of the polynomial p(x) Figure 3: Caricature of the polynomial q(x)

Thus our constructed polynomial, r, has degree Õ( √ n) and approximates NOR to error 1/3, which is optimal by Lemma 2.6.

Informal terminology: polynomials as algorithms

Before moving on to surjectivity, we briefly introduce some terminology that will allow us convey the intuition of more involved constructions by reasoning about polynomials as if they were algorithms.

Consider three Boolean functions p 1 : {0, 1} n → {0, 1}, p 2 : {0, 1} n → {0, 1} and p 3 : {0, 1} n → {0, 1}, and suppose there are deterministic algorithms A 1 , A 2 , and A 3 that compute these Boolean functions exactly. Now it makes sense to say "run algorithm A 1 in input x; if it accepts then output A 2 (x), and if it rejects, then output A 3 (x)." The Boolean function computed by this is A 2 (x) if A 1 (x) = 1 and A 3 (x) if A 1 (x) = 0. Observe that the following polynomial composition of p 1 , p 2 , p 3 computes the same Boolean function: p 1 (x)p 2 (x) + (1p 1 (x))p 3 (x).

We would like to use this terminology to discuss combining polynomials more generally. For polynomials p that approximate Boolean functions by outputting a value in [0, 1] on any input x, we can imagine p(x) as representing the probability that a randomized (or quantum) algorithm accepts on input x, and the same interpretation goes through. We will also use the same terminology for polynomials that output values greater than 1, in which case we cannot interpret the output as a probability, but expressions like p 1 (x)p 2 (x) + (1p 1 (x))p 3 (x) still make sense.

For example, in the previous section we had two polynomials p and q and we constructed the polynomial r(x) = p(x) • q(x) by multiplying the two polynomials together. Another way to think of this is that r is the polynomial obtained when we "run" the polynomial q and output p if it accepts and output 0 if it rejects. This yields the polynomial q(x)p(x) + (1q(x)) • 0 = q(x)p(x). We would like to informally describe polynomial constructions using this language, which will be especially useful when the constructions become more involved. So for example, we would informally describe the polynomial we constructed for the NOR function as follows (Polynomial 1):

Polynomial 1 An informal description of the polynomial approximation for NOR 1: Using q, check if |x| > T (with exponentially small probability of error if indeed |x| > T ). If so, halt and output 0. 2: Using p, compute NOR under the promise that 0 ≤ |x| ≤ T and output the result.

Approximating surjectivity on the hard inputs

To implement the strategy described in Section 3.2 in the context of surjectivity, we first choose a set P of inputs that we consider to be "hard". Since surjectivity can be phrased as asking whether all range items appear at least once in the input, it is natural to consider the hard inputs to be those that have few occurrences of each range item. Intuitively, this is because on such inputs, evidence that any given range item r appears at least once in the input is hard to find.

To this end, we define P as the set of inputs for which every range item appears at most T times, for a parameter T to be chosen later:

More generally, when we consider R-surjectivity, we denote the set of hard inputs P R and define it as

In this section, we will construct a polynomial p R that approximates SURJ R on P R to bounded error, but may be exponentially large outside of P R . The value of T in the definition of P R will be chosen later; for now we only assume that our choice will satisfy T = N Θ (1) , which simplifies some expressions since we have log T = Θ(log N).

Overview of the construction of p R . To construct a polynomial that works on the hard inputs, P R , we first express SURJ R as

where 1[x i = r] is the indicator function that takes value 1 when x i = r and 0 otherwise. Observe that for any fixed r ∈ R, the function 1[x i = r] depends on only log R bits of x and hence can be exactly computed by a polynomial of degree at most log R.

Since our goal in this section is to construct a polynomial p R that approximates SURJ R on all inputs in P R and may be exponentially large outside of P R , we can assume that each inner OR gate in Equation (3.8) is fed an input of Hamming weight at most T . Hence, our approach will be to first construct a low-degree polynomial q that approximates AND |R| • OR N for inputs in H N ≤T |R| . We then obtain the polynomial p R that approximates SURJ R at all inputs in P R by composing q with the indicator functions {1[x i = r]} i∈[N],r∈R . Notice that the degree of p R is at most deg(q) • log R.

To construct q, our approach is as follows. First, we construct a polynomial V T of degree O(T 1/2 log N) that approximates OR N to error O(1/N) at all inputs of Hamming weight at most T . (However, V T (x) may be as large as exp(T 1/2 log N) for inputs x of larger Hamming weight). Invoking Lemma 2.6, we let w be a polynomial of degree Θ(N 1/2 ) that approximates AND |R| to error 1/20, and finally we define q := w •V T . A simple and elegant analysis of Buhrman et al. [25] (cf. Lemma 3.4) allows us to argue that q indeed approximates AND |R| • OR N on H N ≤T |R| .

Preliminary lemmas. Before formally defining and analyzing p R , we record a few important facts about Chebyshev polynomials that will be useful throughout the remainder of this section. (2) For any polynomial p : R → R of degree d with |p(x)| ≤ 1 for all x ∈ [-1, 1], we have that for any x with |x| > 1,

where T d is the Chebyshev polynomial of degree d.

Proof. To establish property (1), we use the fact that for µ > 0, the value of the degree-d Chebyshev polynomial can be written [37, §3.2 Problem 8(f)] as

Property (2) appears as [37, 3.2 Problem 19].

We are now ready to establish the existence of a low-degree polynomial that approximates OR at all inputs of low Hamming weight.

Because p is bounded in [0, 1], this implies

completing the proof.

Formal definition of p R . Let w be a (1/20)-approximating polynomial for AND |R| of degree O(|R| 1/2 ) whose existence is guaranteed by Lemma 2.6. We may assume that w(x) ∈ [0, 1] for all x ∈ {0, 1} n (we will exploit this assumption in the proof of Lemma 3.7 below, as it allows us to apply Lemma 3.6 below to w). Let q := w • V T,1/(20n) . Finally, let us define p R to be the composition of q with the indicator functions {1[

Showing p R approximates SURJ R on P R . Lemma 3.4 implies that:

) . This bound relies on the following elementary lemma.

Lemma 3.6. Let p : R n → R be a multilinear polynomial with p(x) ∈ [0, 1] for all x ∈ {0, 1} n . Then for x ∈ R n , we have

Proof. We prove the lemma by induction on the number of variables n. If n = 0, then p is a constant in the interval [0, 1] and the claim is true. Now suppose the claim is true for n -1 variables, and let p : R n → R with p(x) ∈ [0, 1] for x ∈ {0, 1} n . We begin by decomposing

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71 where q 0 and q 1 are themselves multilinear polynomials. Since p(x) ∈ [0, 1] for all x ∈ {0, 1} n , this is in particular true when x n = 0. Hence q 0 (x ) ∈ [0, 1] for all x ∈ {0, 1} n-1 . Similarly, setting x n = 1 reveals that q 1 (x ) ∈ [0, 1] for all x ∈ {0, 1} n-1 . Now for any x ∈ R n with x = (x 1 , . . . , x n-1 ) we have

where the final inequality uses the inductive hypothesis. This proves the claim. Lemma 3.7. There exists a function a

Proof. The first two cases are an immediate consequence of Lemma 3.5.

To upper bound the value of |p R (x)| for x / ∈ P R , we exploit the structure of p R as a multilinear polynomial w of degree O( √ N) over the variables z 1 , . . . , z |R| , where each z r is the output of the r th polynomial from Lemma 3.3. That is,

If b R (x) range items appear greater than T times, this means that up to b R (x) of the variables z r might take values outside [0, 1]. However, by Lemma 3.3, each of these b R (x) variables is still at most exp( Õ( √ T )). By Lemma 3.6,

since each z r that is in [0, 1] contributes a factor of exactly 1 to the product, whereas each of the remaining b R (x) variables contributes a factor of at most exp( Õ( √ T )) to the product.

Controlling the easy inputs

Intuition. Unlike the example of the NOR function, where all the inputs outside the "hard" set P (cf. Equation (3.1)) were in NOR -1 (1), for surjectivity there are both 0-and 1-inputs outside of the hard set P (cf. Equation (3.6)) . So our remaining task is not simply a matter of constructing a polynomial that detects if the input is outside of P, as it was in the case of the NOR function. However, we will show that, for surjectivity, the inputs outside of P are easy to handle in a different sense-they are easy because we can construct a reduction from inputs outside of P to inputs in P. To gain some intuition, consider the task of designing a randomized algorithm for surjectivity where we want to reduce the general case to the case where there is a set R ⊆ [R] such that all range items r ∈ R have # r (x) ≤ T . To do this, we can simply sample a large number of elements x i and remove from consideration all range items appearing at least once in the sample, because we know these range items all appear in the input at least once. After this step, we have a new set R ⊆ [R] consisting of all range items that have not been seen in the sampling stage. Every r ∈ R is likely to have # r (x) ≤ T because elements that appeared too frequently would have (with high probability) been observed in the sampling stage. Thus it now suffices to solve SURJ R on the input under the assumption that all range items r ∈ R have # r (x) ≤ T .

Informally, the above discussion states that we want to construct the polynomial described in Polynomial 2.

Polynomial 2 Informal description of the polynomial approximation for SURJ We now have to construct a polynomial that represents this algorithmic idea. We have already constructed an (unbounded approximating) polynomial for SURJ R under the promise P R in the previous section, so the second step of this construction is done.

For Step 1 of Polynomial 2, we need to construct a polynomial to represent the idea of sampling input elements and evaluating a polynomial that depends on the sampled elements. To build up to this, consider a deterministic algorithm that queries a subset S ⊆ [N] of input elements, checks if the sampled string equals another fixed string y and outputs 1 if true and 0 if false. If we denote the input x ∈ [R] N restricted to the subset S ⊆ [N] as x S , then this algorithm outputs 1 if and only if x S = y. Interpreting the input as an element of {0, 1} N log R rather than [R] N , it is easy to see that a deterministic query algorithm querying |S| log R bits of x can solve this problem. Consequently, there is a polynomial of degree |S| log R that outputs 1 if x S = y and outputs 0 otherwise. For any fixed S ⊆ [N] and y ∈ [R] |S| , we denote this polynomial by 1 y (x S ).

Now we can construct a polynomial which samples S elements of the input and then outputs a bit depending on the elements seen. Let S ⊆ [N] be a subset of indices with |S| = S. Let f (S, x S ) be an arbitrary Boolean function that tells us whether to output 0 or 1 on seeing the sample (S, x S ). Then the following polynomial samples a random set S of size S, reads the input x restricted to the set S, and outputs the bit f (S, x S ):

Note that for any function f , this is a polynomial of degree S log R in the variables x 1 , . . . , x N , because 1 y (x S ) is a multilinear polynomial over those variables, and f (S, y) is simply a hard-coded bit that does not depend on x. The value of this polynomial on an input x equals

We can now generalize this construction to allow for the possibility that the function f is itself a polynomial. This is what we need to implement Polynomial 2, in which we sample a random set S ⊆ [N] of size S, query x S (using S log R queries), and then run a polynomial that depends on the results. Specifically, if we sample the set S ⊆ [N], and learn that x S equals the string y ∈ [R] |S| , then we want to run the polynomial p R (y) from Lemma 3.7 for the set R(y) of all elements in [R] that do not appear in y, i. e., R(y) = [R] \ {r : ∃i y i = r}.

(3.15)

Formal description of the approximation to surjectivity. Using the tools from Section 3.4.1 and the above discussion, we can now construct a polynomial that corresponds to the informal description in Polynomial 2:

This is a polynomial of degree S log R+max y {deg(p R(y) )} = Õ(S+ √ NT ) = Õ(N 3/4 ), using S = Θ(N 3/4 ) and T = Θ( √ N) (where the factors hidden by the Θ notation will be chosen later). The value of the polynomial on input x is

where recall that R(x S ) is as defined in Equation (3.15). The right hand side of Equation (3.17) is precisely the expected value of the polynomial p R(x S ) (x) when S is a uniformly random set of size S.

We will now show that r(x) is an approximating polynomial for surjectivity, i. e., that for all

is the number of range items r ∈ R that appear in x greater than T times (cf. Equation (3.12)), we compute the value of the polynomial r(x) on an input x:

We now need to compute the value of Pr S [b R(x S ) (x) = b] for each b. Intuitively, this roughly corresponds to the probability that we sample S = Θ(N 3/4 ) elements from the input and miss all bT elements that correspond to the T = Θ( √ N) copies of the b range items that appear at least T times. If we were to sample N/(bT ) elements, the probability of seeing none of the bT elements would be Θ(1). Since we are sampling S = Θ(N 3/4 ) N/(bT ) elements, the probability of not seeing one of the bT elements is exp(-bST /N) = exp(-b • Ω(N 1/4 )). We make this heuristic calculation formal in the following lemma.

is the number of range items r ∈ R that appear in x more than T times, but do not appear in x S .

Proof. To calculate the probability of interest, we begin by analyzing a simplified experiment. Suppose there are b range items r 1 , . . . , r b each appearing greater than T times in x. We compute the probability that none of the items r 1 , . . . , r b appear in the sample x S . If T ≥ N -S, then this probability is zero. Otherwise, by direct calculation, we have for each i = 1, . . . , b,

Hence the probability that none of r 1 , . . . , r b appear is

Now fix an arbitrary x, and let r 1 , . . . , r k be the range items appearing greater than T times in x. Observe that k ≤ N/T . We estimate the probability of interest by taking a union bound over all subsets of r 1 , . . . , r k of size b:

by choosing T = Θ( √ N) and S = Θ(N 3/4 ) appropriately. This shows that the term in (3.21) does not significantly influence the value of the polynomial for any input x.

Thus we have for any input x,

By Lemma 3.7, we know that if b R(x S ) (x) = 0 (and hence x ∈ P R(x S ) ), then p R(x S ) (x) is a (1/10)approximation to SURJ(x). Applying Lemma 3.8 once again shows that

This completes the proof of Theorem 3.1.

Lower bound for surjectivity

The goal of this section is to show the following improved lower bound on the approximate degree of the surjectivity function.

Theorem 4.1. For some N = O(R), the (1/3)-approximate degree of SURJ N,R is Ω(R 3/4 ).

To prove Theorem 4.1, we combine the following theorem with the reductions of Proposition 2.10 and Corollary 2.16.

The proof of Theorem 4.2 entails using dual witnesses for the high approximate degree of AND R and OR N to construct a dual witness for the higher approximate degree of F ≤N . As indicated in Section 1.3, the construction is essentially the same as in [33], except that we observe that a dual witness for OR constructed and used in prior work satisfies an exponentially stronger decay condition than has been previously realized.

The construction can be thought of as consisting of three steps:

Step 1. We begin by constructing a dual witness ψ for the fact that the unbounded approximate degree of the OR N function is Ω √ T even when promised that the input has Hamming weight at most T = Θ( √ R). The dual witness ψ is a small variant of the one in [33], but we give a more careful analysis of its tail decay. In particular, we make use of the fact that for all t ≥ 1, the 1 weight that ψ places on the t-th layer of the Hamming cube is upper bounded by exp(-Ω(t/ √ T ))/t 2 .

Step 2. We combine ψ with a dual witness Φ for AND R to obtain a preliminary dual witness Φ ψ for F = AND R • OR N . The dual witness Φ ψ shows that F has approximate degree

). However, Φ ψ places weight on inputs of Hamming weight larger than N, and hence does not give an unbounded approximate degree lower bound for the promise variant F ≤N .

Step 3. Using Proposition 2.22 we zero out the mass that Φ ψ places on inputs of Hamming weight larger than N, while maintaining its pure high degree and correlation with F ≤N . This yields the final desired unbounded approximate degree dual witness ζ for F ≤N , as per Proposition 2.5.

Step 1: A dual witness for OR N

We begin by constructing a univariate function which captures the properties we need of our inner dual witness for OR N . The construction slightly modifies the dual polynomial for OR N given by Špalek [82]. We provide a careful analysis of its decay as a function of the input's Hamming weight. For all univariate polynomials q : R → R,

Proof of Proposition 4.3. By renormalizing, it suffices to construct a function ω :

For all univariate polynomials q : R → R,

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71

Let c = 8/δ below. We will freely use the fact that since δ ≤ 1/2, we have c ≤ c 2 /(c -1) ≤ 10/δ . Let m = T /2c and define the set

Note that |S| ≥ c 1 √ δ T for some absolute constant c 1 > 0. Define the function

Property (4.6) follows from the following well-known combinatorial identity.

Fact 4.4 (e. g., [43] Equation (5.23) or [63]). Let T ∈ N, and let p be a polynomial of degree less than T . Then

Expanding the binomial coefficient in the definition of ω reveals that

We now use this characterization to establish the improved tail decay property (4.7). This clearly holds for t = 1 with c 2 = 1/10, since |ω(1)| ≤ ω 1 and 170

For t = c, we have

where the first inequality follows from the fact that

. Thus (4.7) holds for t = c, recalling that c 2 = 1/10. For t = 2c j 2 with j ≥ 1, we get

For j ≥ 1, the first factor is bounded by

using the fact that c ≥ 2. We control the second factor by

where the last inequality uses the fact that 1x ≤ e -x for all x. Since

this establishes (4.7). What remains is to perform the correlation calculation to establish (4.5). For t = 1, we observe

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71

Next, we observe that the total contribution of t > c to ω 1 /ω(0) is at most

Next, we calculate

120c by (4.9)

On the other hand,

Combining (4.10) and (4.11), and using the fact that -ω(1) ≥ ω(0) shows that

This establishes (4.5), completing the proof.

The following construction of a dual polynomial for OR N , with N ≥ T , is an immediate consequence of Minsky-Papert symmetrization (Lemma 2.7), combined with Proposition 4.3.

For any polynomial p :

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71

Step 3: Constructing the final dual witness

)

For every polynomial p : ({-1, 1} N ) R → R of degree less than D, we have p, ζ = 0. (

Proof. We start by fixing choices of several key parameters:

is the pure high degree of the dual witness Φ for AND R in Proposition 4.6,

, where c 1 is the constant from Proposition 4.3,

• α = 170/δ = 3400,

), where c 2 is the constant from Proposition 4.3,

be the function constructed in Proposition 4.5 with δ := 1/20. Let Φ : {-1, 1} R → [-1, 1] be the function constructed in Proposition 4.6, and define ξ = Φ ψ. Then by Proposition 2.20, ξ satisfies the following conditions:

)

For every polynomial p of degree less than D, we have ξ , p = 0. (

Recall that ψ was obtained by symmetrizing the function ω constructed in Proposition 4.3. Proposition 2.22 guarantees that for some

), the function ξ can be modified to produce a function ζ :

For every polynomial p of degree less than min{ D, ∆}, we have ζ , p = 0.

Observing that

shows that the function ζ satisfies the conditions necessary to prove Proposition 4.7.

Theorem 4.2 follows by combining Proposition 4.7 with the dual characterization of unbounded approximate degree given in Proposition 2.5. By Corollary 2.16, we conclude that deg(dSURJ N,R ) = Ω(R 3/4 ). Theorem 4.1 follows by Proposition 2.10.

Lower bound for k-distinctness

Our goal is to prove the following lower bound on the approximate degree of the k-distinctness function.

Theorem 5.1. For k ≥ 2 and some N = O k (R), the (1/3)-approximate degree of DIST k N,R is

The same lower bound holds for the quantum query complexity of DIST k N,R .

Here, the notation O k hides factors depending only on k, and Ωk hides factors logarithmic in R and factors depending only on k.

Theorem 5.1 is a consequence of applying the reductions of Proposition 2.13 and Corollary 2.18 to the following, which is the ultimate goal of this section.

The proof of Theorem 5.2 will follow the same basic outline as the proof of Theorem 4.2. We will construct a dual polynomial for G ≤N via the following three steps:

Step 1. We first construct a dual witness ψ showing that the unbounded-approximate degree of the

, even when promised that the input has Hamming weight at most

Moreover, this dual witness satisfies additional conditions that are exploited in Step 2 below.

Step 2. We combine ψ with a dual witness Φ for OR R to obtain a preliminary dual witness Φ ψ for

). However, Φ ψ places weight on inputs of Hamming weight larger than N, and hence does not give an unbounded approximate degree lower bound for the promise variant G ≤N .

Step 3. Using Proposition 2.22 we zero out the mass that Φ ψ places on inputs of Hamming weight larger than N, while maintaining its pure high degree and correlation with G ≤N . This yields the final desired dual witness ζ for G ≤N . Additional Notation. For functions f : X → {-1, 1} and ψ : X → R, define the error regions

These are the regions where ψ disagrees in sign with f . We refer to E + as the set of "false positive" errors made by ψ, and E -as the set of "false negative" errors.

Step 1: A dual witness for THR k N

We begin by constructing a univariate version of our dual witness for THR k N . Properties (5.1) and (5.2) below amount to more refined conditions on the correlation between ω and the (symmetrized) THR k N function. These properties will be needed in order to execute Step 2 of the construction in Section 5.2. Proposition 5.3. Let k, T, N ∈ N with k ≤ T . There exist constants c 1 , c 2 ∈ (0, 1] and a function ω :

∑

)

For all univariate polynomials q : R → R,

)

Proof. If k = 1, then the function defined by ω(0) = 1 2 and ω(1) = -1 2 satisfies the conditions of the proposition for c 1 = c 2 = 1. In what follows, we treat the complementary case where k ≥ 2.

Let E + := {t : ω(t) > 0,t ≥ k}, and E -:= {t : ω(t) < 0,t < k}. By normalizing, it suffices to construct a function ω :

For all univariate polynomials q : R → R,

)

Let c = 2k N 1/k , and let m = T /c . Define the set

Note that |S| = Ω(k -1/2 T 1/2 N -1/(2k) ). Define the polynomial

The signs are chosen so that ω(k) < 0. It is immediate from Fact 4.4 that ω satisfies (5.8) for c 1 = 1/ √ 2. We now show that (5.9) holds. For t = 1, . . . , k, we have

as long as c 2 ≤ 1/2 and k ≥ 2. Since |ω(t)| ≤ ω 1 , the bound holds for t = 1, . . . , k.

For t = c j 2 with j ≥ 1, we expand out the binomial coefficient in the definition of ω to obtain

For t ∈ {0, 1, . . . , k}, we observe that

Meanwhile, for t = c j 2 with j ≥ 1, we get

The first factor is bounded above by k! (ck) k j 2k+1 .

As long as c ≥ 2k and k ≥ 2, this expression is at most

We control the second factor by

where the last inequality uses the fact that 1x ≤ e -x for all x. Hence,

This immediately yields

which establishes (5.9) for all t = c j 2 > k. Moreover, by (5.11)

Hence, since ω(k) < 0,

which gives (5.6). Finally, to establish (5.7), we combine (5.10) and (5.12) to obtain

We calculate

Rearranging and applying the bound (5.13),

Applying Minsky-Papert symmetrization (Lemma 2.7) to ensure that the resulting function has the appropriate pure high degree, Proposition 5.

For any polynomial p :

(5.18)

Refined amplification lemmas

The dual witness Φ for OR R that we construct will itself be obtained as a dual block composition ρ ϕ.

Each constituent dual polynomial will play a distinct role in showing that Φ ψ is a good dual polynomial for OR R • THR k N . The first function ϕ is an "error amplifier" in the sense that ϕ ψ is much better

The second function ρ, on the other hand, is a "degree amplifier" in that it serves to increase the pure high degree of ϕ ψ.

While the amplification results we need are new, they are relatively straightforward extensions of similar results in [29,30,73]. Proofs appear below for completeness.

Amplifying error. The following proposition shows that if ψ is a dual witness for the high approximate degree of a Boolean function f , then there is a dual witness of the form ϕ ψ for OR M • f such that (a) ϕ ψ may make slightly more false positive errors than ψ (by at most a factor of M), and (b) ϕ ψ makes significantly fewer false-negative errors than ψ (exponentially smaller in M).

)

For every M ∈ N, there exists a function ϕ : {-1, 1} M → [-1, 1] with ϕ 1 = 1 and pure high degree 1 such that

(5.23)

Proof. Let ϕ : {-1, 1} M → {-1, 1} be defined such that ϕ(1) = 1/2, ϕ(-1) = -1/2, and ϕ(x) = 0 for all other x. Notice that ∑ (x 1 ,...,x M )∈{-1,1} M ϕ(x 1 , . . . , x M ) = 0 (5.24) so Ψ has pure high degree 1, and that Ψ 1 = 1. We now prove that Equation 5.22 holds. Let λ be the distribution on {-1, 1} m given by λ (x) = |ψ(x)|, and let λ ⊗M be the product distribution on ({-1, 1} m ) M given by λ ⊗M (x 1 , . . . , x M ) = ∏ M i=1 |ψ(x i )|. Since ψ is orthogonal to the constant polynomial, it has expected value 0, and hence the string (. . . , sgn(ψ(x i )), . . . ) is distributed uniformly in {-1, 1} M when one samples (x 1 , . . . , x M ) according to λ ⊗M . This allows us to write

(5.25)

Observe that for any bit b,

where for brevity, we have written A +1 = E + (ψ, f ) and A -1 = E -(ψ, f ). Therefore, as noted in [75], for any given z ∈ {-1, 1} M , the following two random variables are identically distributed:

• The string (. . . , f (x i ), . . . ), when one chooses (. . . , x i , . . . ) from λ ⊗M conditioned on (. . . , sgn(ψ(x i )), . . . ) = z

• The string (. . . , y i z i , . . . ), where y ∈ {-1, 1} M is a random string whose ith bit independently takes on value -1 with probability 2 ∑ x∈A z i |ψ(x)|.

Thus, Expression (5.25) equals

where y ∈ {- (5.22). It now remains to prove the bound (5.23). By an identical argument as above, we have

The only term in the sum corresponds to z = -1, which we argue takes value 1 2 • (2δ -) M . Here, each It follows that Expression (5.27) is at most 1 2 • (2δ -) M , establishing (5.22). This completes the proof.

Amplifying degree. The following proposition states that if ψ is a dual polynomial for a Boolean function f , then there is a dual polynomial ρ ψ for OR M • f with significantly larger pure high degree that does not make too many more false positive and false negative errors than does ψ itself.

Proposition 5.6. Let f : {-1, 1} m → {-1, 1} and ψ : {-1, 1} m → R be functions such that

)

For every M ∈ N there exists a function ρ : {-1, 1} M → R with ρ 1 = 1 and pure high degree

where y ∈ {-1, 1} M is a random string whose ith bit independently takes the value -1 with probability 2 ∑ x∈A z i |ψ(x)|. (Here, we are using the abbreviated notation

We first consider the contribution of the term corresponding to z = 1 to the sum. Here, by a union bound,

Hence, the term z = 1 contributes ϕ(1) • (1 -4Mδ + ) to the sum. Now we consider the contribution of any term corresponding to z = 1. Given such a z, let i * be an index such that z i * = -1. Then we have

We can now lower bound (5.33) by

Then there exists a function Φ : {-1, 1} R → R with Φ 1 = 1 and pure high degree

Proof. Using the construction of Proposition 5.5 with m = N, M = 4 k , and f = THR k N , we first obtain a function ϕ : {-1, 1} 4 k → R with ϕ 1 = 1 and pure high degree 1 such that

Let Φ : {-1, 1} R → R be the dual block composition ρ ϕ. Since the dual block composition preserves 1 -norms (Proposition 2.20, Condition (2.8)) and multiplies pure high degrees (Proposition 2.20, Condition (2.9)), the function Φ itself has 1 -norm 1 and pure high degree Ω(2 -k √ R). The claim now follows from the associativity of dual block composition (Proposition 2.20, Condition (2.10)) and the fact that OR R = OR R/4 k • OR 4 k .

Step 3: Completing the construction

We are now ready to apply Proposition 2.22 to zero out the mass that the construction of Proposition 5.7 places on inputs outside of H N•R ≤N .

Proposition 5.8. Let R be sufficiently large. There exist N = O((2k

)

For every polynomial p : ({-1, 1} N ) R → R of degree less than D, we have p, ζ = 0.

(5.37)

Proof. We start by fixing choices of several key parameters:

is the pure high degree of the dual witness Φ for OR R in Proposition 5.7,

, where c 1 is the constant from Proposition 5.3,

, where c 2 is the constant from Proposition 5.3.

be the function constructed in Proposition 5.7, and define ξ = Φ ψ. Then by Proposition 2.20, ξ satisfies the following conditions:

)

For every polynomial p of degree less than D, we have ξ , p = 0.

(5.40)

Recall that ψ was obtained by symmetrizing the function ω constructed in Proposition 5.3. Proposition 2.22 guarantees that for some

), the function ξ can be modified to produce a function ζ :

For every polynomial p of degree less than min{ D, ∆}, we have ζ , p = 0.

Observing that

shows that the function ζ satisfies the conditions necessary to prove Proposition 5.8.

Theorem 5.2 now follows by combining Proposition 5.8 with the dual characterization of unbounded approximate degree Proposition 2.5. The approximate degree lower bound in Theorem 5.1 is then a consequence of Proposition 2.13 and Corollary 2.18. The quantum query lower bound follows via the standard fact that the ε-error quantum query complexity of f is lower bounded by 1/2 • deg 2ε ( f ) [13].

6 Lower bound for image size testing and its implications

Connecting symmetric promise properties and block compositions of partial functions

For any function f and symmetric function g, Section 2.5 described a connection between the symmetric property

and the partial function

For simplicity and clarity, that discussion was restricted to total functions f and g (in particular, this avoided having to address the possibility that f (g(x 1 ), . . . , g(x R )) is undefined in the definitions of F prop and F ≤N ). Because IST is a partial function, we need to explain that the same connection still holds even when f is a partial function. To do this, we need to introduce the notion of the double-promise approximate degree of F ≤N . Definition 6.4. Let Y ⊂ {-1, 1} R and f : Y → {-1, 1}, and let g : {-1, 1} N → {-1, 1} be a symmetric (total) function. Let G = {x 1 , . . . , x R : (g(x 1 ), . . . , g(x R )) ∈ Y }. Let F ≤N be defined as above. Observe that F ≤N is defined at all inputs in H N•R ≤N ∩ G. The double-promise ε-approximate degree of F ≤N , denoted dpdeg(F ≤N ) is the least degree of a real polynomial p such that:

Observe that in the definition above, no restriction is placed on p(x) for any inputs that are not in

Bun and Thaler's analysis from [33] (cf. Theorem 2.15) applies to partial functions f in the following way. Theorem 6.5 (Bun and Thaler [33]). Let Y ⊂ {-1, 1} R and let f : Y → {-1, 1} be any partial function. Let g : {-1, 1} N → {-1, 1} be any symmetric function. Then for F prop and F ≤N defined above, and for any ε > 0, we have deg ε (F prop ) ≥ dpdeg ε (F ≤N ).

We will require the following dual formulation of dpdeg ε (F ≤N ).

Proposition 6.6. Let F ≤N and G be defined as above. Then dpdeg ε (F ≤N ) ≥ d if and only if there exists a function ψ : {-1, 1} n → R satisfying the following conditions. purposes, it will not be essential to exploit such a strong correlation guarantee-rather, we are interested in Φ ψ because most of its " 1 -mass" lies on inputs either with full image or tiny image (i. e., most of its mass lies in the domain of GapAND γ R • OR N ). As in Corollary 6.8, let G denote the set of all inputs on which GapAND

The analysis in these prior works [21,30] implies that Φ ψ satisfies the following three conditions.

For any polynomial p :

where c 1 is the constant from Proposition 4.5. Indeed, Properties (6.7) and (6.9) are immediate from Proposition 2.20 on the properties of dual block composition. For completeness, we prove that Property (6.8) holds in Section 6.1.3 below, making use of the fact that δ = γ/4 and taking R to be sufficiently large. Proposition 2.22 (with α and β set as above) guarantees that for some

For every polynomial p of degree less than D := min{ D, ∆}, we have ζ , p = 0.

Observing that

shows that the function ζ satisfies the conditions necessary to prove Theorem 6.2 via Proposition 6.6.

6.1.3 Proof of Condition (6.8) Lemma 6.9. Let δ > 0, γ > 2δ , and let

] be any dual witness for OR N such that ψ 1 = 1, ψ, 1 = 0, and ψ,

The proof of Lemma 6.9 crucially relies on a special property, called one-sided error, that is satisfied by any dual polynomial for OR. Definition 6.10. Let f : {-1, 1} N → {-1, 1} and let ψ : {-1, 1} N → R. We say that ψ has one-sided error with respect to f if for all x ∈ {-1, 1} N , f (x) = 1 =⇒ ψ(x) > 0.

(6.10)

The following lemma shows that any dual witness for the OR N function has one-sided error.

Lemma 6.11 (Gavinsky and Sherstov [41]). Let ψ : {-1, 1} N → R be a function with pure high degree at least 1 such that ψ, OR N > 0. Then ψ has one-sided error with respect to OR N .

In particular, if ψ is such a dual witness for OR N , then we have

where the sets A +1 and A -1 are, respectively, the sets of false positive and false negative errors given by

Proof of Lemma 6.9. We begin by observing that the quantity of interest can be written as

We estimate each term of Expression (6.12) separately, beginning with the first term. Just as in the proofs of Proposition 5.5 and Proposition 5.6, we have

where y ∈ {-1, 1} R is a random string whose ith bit independently takes the value -1 with probability 2 ∑ x∈A z i |ψ(x)|. For z = -1, we have by (6.11) that 2 ∑ x∈A -1 |ψ(x)| = 0, so the contribution of the corresponding term to the sum is 1/2. For z = 1, we use the fact that 2

Hence, the first summand of (6.12) is at least 1δ R .

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71

We now estimate the second summand, 2 ∑ x / ∈G |(Φ ψ)(x)|. As in the proofs of Proposition 5.5 and Proposition 5.6, we let λ denote the distribution with probability mass function λ

We analyze each term of this sum separately. For the first term, observe that by one-sided error of ψ, it follows that if x = (x 1 , . . . , x R ) is any input sgn(ψ(x i )) = -1 for all i then OR N (x i ) = -1 for all i. Thus we are guaranteed that x ∈ G, so the contribution of the first summand is zero. To analyze the second summand, let us denote by r i ∈ {0, 1} the indicator random variable for the event OR N (x i ) = -1 when x i is drawn from the conditional distribution (λ | sgn(ψ(x i )) = 1). Then

by the multiplicative Chernoff bound. 6 Thus, we have

Putting everything together, we see that Expression (6.12) is at least 1δ Rexp (-(γδ )R/3) as we wanted to show.

Lower bound for SDU

The goal of this section is to derive a lower bound for approximating the statistical distance of an input distribution from uniform up to some additive constant error. We formalize this problem as follows.

Given an input (s 1 , . . . , s N ) ∈ [R] N , and i ∈ [R], let f i = |{ j : s j = i}|, and let p be the probability distribution over

Above, 1 2 ∑ R i=1 |p i -1/R| is the statistical distance between p and the uniform distribution. The SDU problem reduces to IST in the sense that any approximating polynomial for SDU implies the existence of an approximation to IST of the same degree. Hence, the approximate degree of SDU is at least as large as that of IST. For intuition as to why this is true, let us relate IST N,R (s 1 , . . . , s N ) = 1, then at most R/2 indices i ∈ [R] appear in the input list, so the list represents a distribution with statistical distance at least 1/2 from uniform. Thus, an approximating polynomial for SDU 1/2,0 N,R is also an approximating polynomial for IST 1/2 N,R . We will actually need a more general relationship between the approximate degrees of SDU and IST to handle the fact that we cannot take N to be exactly equal to R in the IST lower bound, as well as to handle the occurrences of dummy items in the definition of IST. Theorem 6.14. For some N = O(R), and some constants 0 < γ

The same lower bound applies to the quantum query complexity of SDU

Proof. Fix R > 0, let c be the constant from Theorem 6.2, γ < (2/3c) 2 be a sufficiently small constant, and

0 , we can equivalently interpret them as elements of [R + 1] N , i. e., as inputs to SDU

(-1), and (-1) define a probability distribution over [R + 1] with support size at least R, with all probabilities being integer multiples of 1/N = γ 1/2 /(cR), the statistical distance between any such distribution and the uniform distribution is at most 1 -R/N = 1γ 1/2 /c. This follows from the following calculation. Amongst probability distributions (p 1 , . . . , p R+1 ) over [R + 1] with support size at least R and all probabilities p i being integer multiples of 1/N, it is not hard to see that one maximizes the statistical distance from the uniform distribution over [R + 1] by setting p 1 = 1 -R-1 N , p 2 = p 3 = • • • = p R = 1/N, and p R+1 = 0. The statistical distance from uniform is

where we have assumed that N ≥ R + 1, which is true for sufficiently small choice of γ.

Similarly, since inputs in IST γ N,R -1

(1) define a probability distribution over [R + 1] with support size at most γ • R + 1, the statistical distance between any such distribution and the uniform distribution is at least 1 -3γ/2. To see this, let p = (p 1 , . . . , p R+1 ) be any distribution of support size at most γ • R, and let S = {i : p i = 0} and S be the complement of S. Then the statistical distance of p from uniform is at least

It is an easy consequence of the above that any ε-approximating polynomial of degree d for SDU

implies an approximation to IST γ N,R of the same degree (i. e., that deg ε (IST γ N,R ) ≤ d). Theorem 6.14 then follows from Theorem 6.2.

Lower bound for entropy comparison and approximation

Given a distribution p over [R], the Shannon entropy of p, denoted H(p), is defined to be H(p) := ∑ i∈[R] p i log 2 (1/p i ). Following Goldreich and Vadhan [42], we define a partial function GapCmprEnt 4N,2R for some constants α, β such that αβ = λ . This reduction (described next for completeness) implies that deg ε (SDU

For completeness, we sketch this transformation, closely following the presentation of Goldreich and Vadhan [42]. At a high level, the reduction transforms an input in [R] N to SDU The entropy of p 1 is always v + 1, where v = 1 2 H(p) + 1 2 log 2 (R). As for the entropy of p 2 , if p is far from the uniform distribution, then the selection bit s will be essentially determined by the sample r. Hence, the entropy of p 2 will be approximately v, which is noticeably smaller than the entropy of p 1 . On the other hand, if the two input distributions are close then (even conditioned on the sample selected) the selection bit s will be almost random and so H(p 2 ) ≈ v + 1, which is approximately the same as H(p 1 ). Quantitatively, Vadhan [88] shows that if the statistical distance between p and the uniform distribution is δ , then 1δ ≤ H(p 1 ) -H(p 2 ) ≤ H((1 + δ )/2).

Since we are considering distributions specified as vectors in [R] N , this transformation can be equivalently described as follows. Assume for simplicity that R divides N. If p is specified by a vector u in [R] N , then p 2 is specified by a vector w in ([R] × {0, 1}) 4N defined as follows. For all i ∈ [N] and j ∈ {0, 1}, w i, j = (u i , 0), and for j ∈ {2, 3}, w i, j = ( Ri/N , 1). Similarly, p 1 is specified by a vector v in ([R] × {0, 1}) 4N . For i ∈ [R] and j ∈ {0, 1}, v i, j = (u i , j), and for j ∈ {2, 3}, v i, j = ( Ri/N , j -2). Observe that when representing u, v, and w as vectors in {-1, 1} N log 2 (R) or {-1, 1} 4N•log 2 (R) , each bit of v and w depends on at most one bit of u.

Recall that in the statement of Theorem 6.14, γ 1 = 1-3γ/2 and γ 2 = 1-γ 1/2 /c, where γ is an arbitrary constant less than (2/3c) 2 , where c > 1 is the constant from Theorem 6.2. Clearly, H((1 + γ 1 )/2)) = H(1 -3γ/4) = H(3γ/4). Using the fact that for any p ∈ [0, 1/2], H(p) = -p log 2 (p) -(1p) log 2 (1p) ≤ -2p log 2 (p) ≤ 6p 3/4 , it follows that for some constant γ ≤ 1/(648c 4 ), we have H(3γ/4) < γ 1/2 /c. Hence, Vadhan's reduction from SDU Clearly, a quantum query algorithm that approximates entropy up to additive error (αβ )/4 can be used to solve GapCmprEnt α,β 4N,2R , by (approximately) computing the entropies of each of the two input THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71 distributions, and determining whether the difference is at most (β + α)/2. Hence, Theorem 6.15 implies the following lower bound for approximating entropy to additive error αβ . Corollary 6.16. Let N = c • R for a sufficiently large constant c. Interpret an input in [R] N as a distribution p in the natural way (i. e., for each j ∈ [R], p j = f j /N, where f j is the number of times j appears in the input). There is a constant ε > 0 such that any quantum algorithm that approximates the entropy of p up to additive error ε with probability at least 2/3 requires Ω(R 1/2 ) queries.

Open problems

The most obvious direction for future work is to extend our techniques to determine the approximate degree and quantum query complexity of additional problems of interest in the study of quantum algorithms. These include triangle finding problem [53,59], graph collision [59], and verifying matrix products [26,51]. It would also be interesting to close the gap between our Ω(n 3/4-1/(2k) ) lower bound for k-distinctness and Belovs' O n 3/4-1/(2 k+2 -4 ) upper bound, especially for small values of k (e. g., k = 3). Note that Belovs' upper bound is known to be tight for k equal to 1 and 2 [3].

Although we prove a lower bound of Ω(R 1/2 ) for SDU = Ω(R 1/2 ). It may be tempting to suspect that Theorem 6.14 implies an Ω(R 1/2 ) lower bound on SDU 2/3,1/3 N,R

, by invoking the well-known Polarization Lemma of Sahai and Vadhan [67]. The Polarization Lemma reduces SDU γ 1 ,γ 2 N,R for any pair of constant γ 1 , γ 2 with γ 2 < γ 2 1 to SDU 2/3,1/3 N ,R for an appropriate choice of N and R . Unfortunately, N and R may be polynomially larger than N and R, so this reduction does not give an Ω(R 1/2 ) lower bound for SDU 2/3,1/3 N,R itself.

THEORY OF COMPUTING, Volume 16 (10), 2020, pp. 1-71 Another important direction is to determine the approximate degree of specific classes of functions, especially polynomial size DNF formulae, and AC 0 circuits. As mentioned in the previous subsection, our k-distinctness lower bound (Theorem 1.2) gives the best known lower bound on polynomial size DNFs. A compelling candidate for improving this lower bound is the k-sum function, which may have approximate degree as large as Θ(n k/(k+1) ) (it is known that the quantum query complexity of k-sum is Θ(n k/(k+1) ) [8,18]). On the upper bounds side, it may be possible to extend the techniques underlying our Õ(n 3/4 ) upper bound on the approximate degree of SURJ to yield a sublinear upper bound for every DNF formula of polynomial size. Open Problem 7.1. For every constant c > 0 and every DNF formula f : {-1, 1} n → {-1, 1} of size at most n c , is there a δ > 0 (depending only on c) such that deg( f ) = O(n 1-δ )?

A positive answer to Open Problem 7.1 would have major algorithmic consequences, including a subexponential time algorithm for agnostically learning DNF formulae [46] (and PAC learning depth three circuits [49]) of any fixed polynomial size.

For general AC 0 circuits, an Ω(n 1-δ ) approximate degree lower bound is already known [33]. It would be very interesting to improve this lower bound to an optimal Ω(n). Until recently, SURJ was a prime candidate for exhibiting such a lower bound. However, owing to Sherstov's upper bound [78] and Theorem 1.1, SURJ is no longer a candidate function. However, we are optimistic about the following closely related candidate. An approximate majority function is any total Boolean function that evaluates to -1 (or +1) whenever at least 2/3 of its inputs are -1 (+1, respectively). It is well-known (via the probabilistic method) that there are approximate majorities computable by depth 3 circuits of quadratic size and logarithmic bottom fan-in [4]. It is possible that every approximate majority has approximate degree Ω(n); proving this would resolve a question of Srinivasan [40].