2 papers
cs.DS2026
Testing Graph Properties with the Container Method
Eric Blais, Cameron Seth
We establish nearly optimal sample complexity bounds for testing the -clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs…
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…