Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum query complexity:
TR05-041 | 12th April 2005
Shengyu Zhang

(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Revisions: 2

The Local Search problem, which finds a
local minimum of a black-box function on a given graph, is of both
practical and theoretical importance to many areas in computer
science and natural sciences. In this paper, we show that for the
Boolean hypercube $\B^n$, the randomized query complexity of Local
more >>>

TR11-040 | 22nd March 2011
Alexander A. Sherstov

Strong Direct Product Theorems for Quantum Communication and Query Complexity

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

TR17-169 | 24th October 2017
Mark Bun, Robin Kothari, Justin Thaler

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

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

TR18-010 | 14th January 2018
Alexander A. Sherstov

Algorithmic polynomials

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

ISSN 1433-8092 | Imprint