35 citations · 98 across the 9 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
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…