Abstract. We consider the problem of testing whether a Boolean function f: {−1, 1} n → {−1, 1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w1x1+w2x2+ · · ·+wnxn) where the weights wi take values in {−1, 1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±1-weight halfspace versus ɛ-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(log n) queries. We complement this lower bound with a sublinear upper bound showing that O ( √ n·poly ( 1 ɛ)) queries suffice. 1
Abstract. We consider the problem of testing whether a Boolean function f: {−1, 1} n → {−1, 1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w1x1+w2x2+ · · ·+wnxn) where the weights wi take values in {−1, 1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±1-weight halfspace versus ɛ-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(log n) queries. We complement this lower bound with a sublinear upper bound showing that O ( √ n·poly ( 1 ɛ)) queries suffice. 1
Abstract We study the approximation of halfspaces h:{0,1}n→{0,1} h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus 2−Ω(n) 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus Ω(n) Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus Ω(n/4n) Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-n input is k or it is l. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of (nk,nl) and sufficiently large n, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of (nk,nl) with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain [n]. Specifically, we present a nonadaptive algorithm that, given inputs ε ∊ (0,1), s ∊ ℕ, and oracle access to a function, ε-tests convexity in O(log(s)/ε), where s is an upper bound on the number of distinct discrete derivatives of the function. We also show that this bound is tight. Since s ≤ n, our query complexity bound is at least as good as that of the optimal convexity tester (Ben Eliezer; ITCS 2019) with complexity ; our bound is strictly better when s = o(n). The main contribution of our work is to appropriately parameterize the complexity of convexity testing to circumvent the worst-case lower bound (Belovs et al.; SODA 2020) of expressed in terms of the input size and obtain a more efficient algorithm.