Cameron Seth

collaborators

3 papers

math.CO2026

A quantitative container characterization of one-sided testability

Gaia Carenini, Cameron Seth, Yuichi Yoshida

We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira.…

cs.DS2026

Testing the Independent Set Property in Hypergraphs

Elena Grigorescu, Shreya Nasa, Cameron Seth

The optimal sample complexity of testing if an $n$ -vertex graph has an independent set of size $ρ n$ , or is $ε$ -far from having an independent set of size $ρ n$ , was establ…

cs.DS2025

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…