37 citations · 143 across the 23 of their papers we have counts for
33 papers
Distributional Quantum Query Complexity
Shalev Ben-David, M. H. Ebtehaj
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting for all Boolean functions…
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…
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…
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…
Direct Product Theorems for Randomized Query Complexity
Shalev Ben-David, Eric Blais
We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing copies of a function , even with a smal…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1167
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…