All reports by Author Shalev Ben-David:

__
TR16-087
| 30th May 2016
__

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

__
TR16-084
| 23rd May 2016
__

Shalev Ben-David#### Low-Sensitivity Functions from Unambiguous Certificates

__
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-203
| 13th December 2015
__

Scott Aaronson, Shalev Ben-David#### Sculpting Quantum Speedups

__
TR15-175
| 5th November 2015
__

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

__
TR15-108
| 30th June 2015
__

Shalev Ben-David#### A Super-Grover Separation Between Randomized and Quantum Query Complexities

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

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

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

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

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

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