Showing 2026 · cs.DSShow all
2 papers · 2 filters
cs.DS2026
Testing Implies Distance Estimation with Polynomial Loss
Gaia Carenini, Cameron Seth
A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A p…
cs.DS2026
Testing the Independent Set Property in Hypergraphs
Elena Grigorescu, Shreya Nasa, Cameron Seth
The optimal sample complexity of testing if an -vertex graph has an independent set of size , or is -far from having an independent set of size , was establ…