{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihbxxjkbtvy2t4aspeagtzzcak5chm23dkmir2euoidm7z66olsqm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf4amde722d2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.15341v1",
  "publishedAt": "2026-02-18T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yuichi Yoshida"
  ],
  "textContent": "**Authors:** Yuichi Yoshida\n\nWe study monotonicity testing of real-valued functions on directed acyclic graphs (DAGs) with $n$ vertices. For every constant $δ>0$, we prove a $Ω(n^{1/2-δ}/\\sqrt{\\varepsilon})$ lower bound against non-adaptive two-sided testers on DAGs, nearly matching the classical $O(\\sqrt{n/\\varepsilon})$-query upper bound. For constant $\\varepsilon$, we also prove an $Ω(\\sqrt n)$ lower bound for randomized adaptive one-sided testers on explicit bipartite DAGs, whereas previously only an $Ω(\\log n)$ lower bound was known. A key technical ingredient in both lower bounds is positive-matching Ruzsa--Szemerédi families. On the algorithmic side, we give simple non-adaptive one-sided testers with query complexity $O(\\sqrt{m\\,\\ell}/(\\varepsilon n))$ and $O(m^{1/3}/\\varepsilon^{2/3})$, where $m$ is the number of edges in the transitive reduction and $\\ell$ is the number of edges in the transitive closure. For constant $\\varepsilon>0$, these improve over the previous $O(\\sqrt{n/\\varepsilon})$ bound when $m\\ell=o(n^3)$ and $m=o(n^{3/2})$, respectively.",
  "title": "Testing Monotonicity of Real-Valued Functions on DAGs"
}