779 citations · 2.6k across the 35 of their papers we have counts for
Showing 2015 · cs.CCShow all
2 papers · 2 filters
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★ 2 cited
Separating decision tree complexity from subcube partition complexity
Robin Kothari, David Racicot-Desloges, Miklos Santha
The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose de…