2 citations · 4 across the 4 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
A Super-Grover Separation Between Randomized and Quantum Query Complexities
Shalev Ben-David
We construct a total Boolean function satisfying , refuting the long-standing conjecture that for all total Boolean functions. Assumi…