Near-Linear Lower Bounds for Testing Directed Acyclicity
We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetilde\Omega(n^{5/9})$ for one-s...