{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreideosm7e5rmke2t5mpzhrygy76ozxllccb75rq4gegjbedadn57ai",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjloado54i72"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.13577v1",
  "publishedAt": "2026-04-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yuichi Yoshida"
  ],
  "textContent": "**Authors:** Yuichi Yoshida\n\nWe study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constants $d_0\\in\\mathbb{N}$ and $\\varepsilon>0$ such that for every constant $d\\ge d_0$, any one-sided $\\varepsilon$-tester for acyclicity on $n$-vertex digraphs of maximum outdegree at most $d$ requires $\\widetildeΩ(n^{2/3})$ queries. This improves the previous $\\widetildeΩ(n^{5/9})$ lower bound for one-sided testing of acyclicity in the same model. We also prove that, under the same degree assumption, any two-sided $\\varepsilon$-tester requires $Ω(\\sqrt n)$ queries, improving the previous $Ω(n^{1/3})$ lower bound. We further prove an $Ω(n)$ lower bound for tolerant testing for some absolute constant outdegree bound $d$ by reduction from bounded-degree $3$-colorability.",
  "title": "Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model"
}