13 citations · 25 across the 15 of their papers we have counts for
Showing 2020 · cs.CCShow all
2 papers · 2 filters
cs.CC2020
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David, Eric Blais
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of part…
cs.CC2020★ 1 cited
A New Minimax Theorem for Randomized Algorithms
Shalev Ben-David, Eric Blais
The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function with finite domain, there is a distribution over the domain of such that comput…