From the 1 of 3 linked papers with an AI index.
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 paper presents a new upper bound on the sample complexity for testing whether a q‑uniform hypergraph has an independent set of size ρn, improving previous results by reducing t…
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 g…