35 citations · 98 across the 9 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CC2015★ 19 cited
Nearly optimal separations between communication (or query) complexity and partitions
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 r…
cs.CC2015
Almost quadratic gap between partition complexity and query/communication complexity
Andris Ambainis, Martins Kokainis
We show nearly quadratic separations between two pairs of complexity measures: 1. We show that there is a Boolean function with where is t…
quant-ph2015
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, Jānis Iraids +2
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function is computable by a 1-query quantum alg…