Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Robin Kothari:

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 >>>

TR16-087 | 30th May 2016
Shalev Ben-David, Robin Kothari

Randomized query complexity of sabotaged and composed functions

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 >>>

TR16-072 | 4th May 2016
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Separations in communication complexity using cheat sheets and information complexity

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized
communication complexity for a ... more >>>

TR15-195 | 3rd December 2015
Robin Kothari

Nearly optimal separations between communication (or query) complexity and partitions

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

TR15-175 | 5th November 2015
Scott Aaronson, Shalev Ben-David, Robin Kothari

Separations in query complexity using cheat sheets

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 >>>

ISSN 1433-8092 | Imprint