All reports by Author Robin Kothari:

__
TR21-016
| 16th February 2021
__

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari#### Unambiguous DNFs from Hex

Revisions: 1

__
TR20-066
| 28th April 2020
__

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal#### Quantum Implications of Huang's Sensitivity Theorem

__
TR19-089
| 21st June 2019
__

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal#### Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

__
TR19-062
| 18th April 2019
__

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

__
TR18-156
| 8th September 2018
__

Mark Bun, Robin Kothari, Justin Thaler#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revisions: 2

__
TR17-169
| 24th October 2017
__

Mark Bun, Robin Kothari, Justin Thaler#### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

__
TR16-087
| 30th May 2016
__

Shalev Ben-David, Robin Kothari#### Randomized query complexity of sabotaged and composed functions

__
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

__
TR15-195
| 3rd December 2015
__

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

__
TR15-175
| 5th November 2015
__

Scott Aaronson, Shalev Ben-David, Robin Kothari#### Separations in query complexity using cheat sheets

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>>

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... more >>>

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

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

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

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

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

Robin Kothari

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

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