Showing 2026Show all
2 papers · 1 filter
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 -vertex graph has an independent set of size , or is -far from having an independent set of size , was establ…