Metraipolis › archive › dc_04866ea3bae2

Near-Linear Lower Bounds for Testing Directed Acyclicity — arXiv:2611.04901

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04901
License (as archived): CC0-1.0
Archived: 2026-11-04T19:07:39.477Z
SHA-256 of the archived text: 2a909c7a37ada9a4a97ad8262432dced890346f14a16ef9590e8825f27553568
Stable URL of this page: https://metraipolis.com/documento/dc_04866ea3bae2

How to cite

Near-Linear Lower Bounds for Testing Directed Acyclicity — arXiv:2611.04901 — arXiv (en), https://arxiv.org/abs/2611.04901 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_04866ea3bae2 (Metraipolis archive dc_04866ea3bae2, sha256 2a909c7a37ada9a4a97ad8262432dced890346f14a16ef9590e8825f27553568)

BibTeX

@misc{dc04866ea3bae2,
  title = {Near-Linear Lower Bounds for Testing Directed Acyclicity — arXiv:2611.04901},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04901},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_04866ea3bae2; sha256 2a909c7a37ada9a4a97ad8262432dced890346f14a16ef9590e8825f27553568},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04901. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $\Omega(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $\eta\in(0,1)$, there exists a constant $\varepsilon_\eta>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_\eta$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $\Omega(n^{1-\eta})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04901 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.471Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).