13 citations · 25 across the 15 of their papers we have counts for
8 papers · 1 filter
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…
A Characterization of Constant-Sample Testable Properties
Eric Blais, Yuichi Yoshida
We characterize the set of properties of Boolean-valued functions on a finite domain that are testable with a constant number of samples. Specifically, we show that a…
Testing submodularity and other properties of valuation functions
Eric Blais, Abhinav Bommireddi
We show that for any constant and , it is possible to distinguish functions that are submodular from those that are -far from every sub…
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément L. Canonne, Talya Eden +2
A function is a -junta if it depends on at most of its variables. We consider the problem of tolerant testing of -juntas, where the test…