Testing Connectedness of Images

We investigate algorithms for testing whether an image is connected. Given a proximity parameter $ε\in(0,1)$ and query access to a black-and-white image represented by an $n\times n$ matrix of Boolean pixel values, a (1-sided error) connectedness tester accepts if the image is connected and rejects with probability at least 2/3 if the image is $ε$-far from connected. We show that connectedness can be tested nonadaptively with $O(\frac 1{ε^2})$ queries and adaptively with $O(\frac{1}{ε^{3/2}} \sqrt{\log\frac{1}ε})$ queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity $O(\frac 1{ε^2}\log \frac 1ε)$ and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make $Ω(\frac 1ε\log \frac 1ε)$ queries.