Showing cs.CCShow all
2 papers · 1 filter
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…
cs.CC2025
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…