Cameron Seth

STOC Conference 2025 Conference Paper

A Tolerant Independent Set Tester

• Cameron Seth

We give nearly optimal bounds on the sample complexity of (Ω(є),є)-tolerant testing the ρ-independent set property in the dense graph setting. In particular, we give an algorithm that inspects a random subgraph on O (ρ 3 /є 2 ) vertices and, for some constant c , distinguishes between graphs that have an induced subgraph of size ρ n with fewer than є/ c log 4 (1/є) n 2 edges from graphs for which every induced subgraph of size ρ n has at least є n 2 edges. Our sample complexity bound matches, up to logarithmic factors, the recent upper bound by Blais and Seth (2023) for the non-tolerant testing problem, which is known to be optimal for the non-tolerant testing problem based on a lower bound by Feige, Langberg and Schechtman (2004). Our main technique is a new graph container lemma for sparse subgraphs instead of independent sets. We also show that our new lemma can be used to generalize one of the classic applications of the container method, that of counting independent sets in regular graphs, to counting sparse subgraphs in regular graphs.

STOC Conference 2024 Conference Paper

New Graph and Hypergraph Container Lemmas with Applications in Property Testing

• Eric Blais
• Cameron Seth

FOCS Conference 2023 Conference Paper

Testing Graph Properties with the Container Method

• Eric Blais
• Cameron Seth

We establish nearly optimal sample complexity bounds for testing the $\rho$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on n vertices that have a $\rho n$-clique from graphs for which at least $\epsilon n^{2}$ edges must be added to form a $\rho n$-clique by sampling and inspecting a random subgraph on only $\tilde{O}\left(\rho^{3} / \epsilon^{2}\right)$ vertices. We also establish new sample complexity bounds for $\epsilon$-testing k-colorability. In this case, we show that a sampled subgraph on $\tilde{O}(k / \epsilon)$ vertices suffices to distinguish k-colorable graphs from those for which any k-coloring of the vertices causes at least $\epsilon n^{2}$ edges to be monochromatic. The new bounds for testing the $\rho$-clique and k-colorability properties are both obtained via new extensions of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.