Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CAMERON SETH:
All reports by Author Cameron Seth:

TR26-144 | 13th August 2026
Gaia Carenini, Cameron Seth, Yuichi Yoshida

A Quantitative Container Characterization of One-Sided Testability

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. For hereditary graph properties, we prove that one-sided testability is quantitatively equivalent to the existence of suitable hypergraph containers, a central and widely used tool in ... more >>>




ISSN 1433-8092 | Imprint