2 citations · 4 across the 6 of their papers we have counts for
Showing 2026Show all
3 papers · 1 filter
cs.CC2026
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…
cs.CC2026
The Information Complexity of Decision Trees
Avantika Agarwal, Shalev Ben-David, Eric Blais
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size…
cs.CC2026
Monte Carlo to Las Vegas for Recursively Composed Functions
Bandar Al-Dhalaan, Shalev Ben-David
For a (possibly partial) Boolean function as well as a query complexity measure which maps Boolean functions to real numbers, define the compositio…