Distance-Sensitive Property Testing Lower Bounds

Joshua Brody, Pooya Hatami

In this paper, we consider several property testing problems and ask how the query complexity depends on the distance parameter $\eps$. We achieve new lower bounds in this setting…