Cameron Seth

collaborators

Showing cs.DSShow all

2 papers · 1 filter

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…