13 citations · 25 across the 15 of their papers we have counts for
24 papers
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…
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…
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais, Cameron Seth
The graph and hypergraph container methods are powerful tools with a wide range of applications across combinatorics. Recently, Blais and Seth (FOCS 2023) showed that the graph con…
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 o…
Testing and Learning Convex Sets in the Ternary Hypercube
Hadley Black, Eric Blais, Nathaniel Harms
We study the problems of testing and learning high-dimensional discrete convex sets. The simplest high-dimensional discrete domain where convexity is a non-trivial property is the…
Randomised Composition and Small-Bias Minimax
Shalev Ben-David, Eric Blais, Mika Göös +1
We prove two results about randomised query complexity . First, we introduce a "linearised" complexity measure and show that it satisfies an inner-opti…