5 papers
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1144
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…
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…
Oracle Separations for the Quantum-Classical Polynomial Hierarchy
Avantika Agarwal, Shalev Ben-David
We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum…
Separations in query complexity for total search problems
Shalev Ben-David, Srijita Kundu
We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we al…