779 citations · 2.6k across the 35 of their papers we have counts for
6 papers · 1 filter
Randomized query complexity can beat certificate complexity
Shalev Ben-David, Robin Kothari
A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query…
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari +1
Suppose we have randomized decision trees for an outer function and an inner function . The natural approach for obtaining a randomized decision tree for the composed functi…
Randomized query complexity of sabotaged and composed functions
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 B…
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…
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…