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.…