Howard Barnum, Michael Saks

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

Scott Aaronson

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Jorge Castro

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>>

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can

efficiently construct (using \emph{arithmetization}) a low-degree

polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all

points in the Boolean cube $\{0,1\}^n$; the constructed polynomial

$p$ can be interpreted as a polynomial over an arbitrary field

$\mathbb{F}$. The problem ...
more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Scott Aaronson, Andris Ambainis

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

Ben Reichardt

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

Andrew Drucker

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.

We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm

has success probability at ...
more >>>

Ben Reichardt

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>

Ashwin Nayak

We describe a reduction from the problem of unordered search(with a unique solution) to the problem of inverting a permutation. Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction helps us bypass the Bennett-Bernstein-Brassard-Vazirani hybrid argument (1997} and the Ambainis quantum adversary ... more >>>

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>>

Scott Aaronson

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

Jiapeng Zhang

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

Doerr Benjamin, Winzen Carola

We show that the black-box complexity with memory restriction one of the $n$-dimensional $\onemax$ function class is at most $2n$. This disproves the $\Theta(n \log n)$ conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544).

more >>>Gillat Kol, Ran Raz

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. ... more >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>Nikos Leonardos

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>>

Loïck Magnin, Jérémie Roland

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,

Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

Scott Aaronson, Andris Ambainis

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized

query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree

of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ...
more >>>

Shalev Ben-David

We construct a total Boolean function $f$ satisfying

$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing

conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions.

Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions,

we improve this to $R(f)=\tilde{\Omega}(Q(f)^3)$.

Our construction is motivated by the Göös-Pitassi-Watson function

but does not ...
more >>>

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>>

Scott Aaronson, Shalev Ben-David

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

Pavel Hubacek, Eylon Yogev

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>

Shalev Ben-David

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>>

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Alexander Smal, Navid Talebanfard

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around $n/k$ ... more >>>

Toniann Pitassi, Morgan Shirley, Thomas Watson

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Tomer Grossman, Ilan Komargodski, Moni Naor

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries.

Given $\epsilon \in (0,1)$, ... more >>>

Ian Mertz, Toniann Pitassi

Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a ... more >>>

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

Scott Aaronson, DeVon Ingram, William Kretschmer

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>

Meghal Gupta, Naren Manoj

Given query access to a monotone function $f\colon\{0,1\}^n\to\{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star}$, we design an algorithm that outputs a size-$C(f)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this ... more >>>