{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie7g4mt57vhrpl5m2x4dwmb6f3fipz274wwf7bpcaos5hxhybfqwq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3miidxcswg5p2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.00268v1",
  "publishedAt": "2026-04-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Xi Chen",
    "Yuhao Li",
    "Mihalis Yannakakis"
  ],
  "textContent": "**Authors:** Xi Chen, Yuhao Li, Mihalis Yannakakis\n\nWe give an $O(\\log^2 n)$-query algorithm for finding a Tarski fixed point over the $4$-dimensional lattice $[n]^4$, matching the $Ω(\\log^2 n)$ lower bound of [EPRY20]. Additionally, our algorithm yields an ${O(\\log^{\\lceil (k-1)/3\\rceil+1} n)}$-query algorithm for any constant $k$, improving the previous best upper bound ${O(\\log^{\\lceil (k-1)/2\\rceil+1} n)}$ of [CL22]. Our algorithm uses a new framework based on \\emph{safe partial-information} functions. The latter were introduced in [CLY23] to give a reduction from the Tarski problem to its promised version with a unique fixed point. This is the first time they are directly used to design new algorithms for Tarski fixed points.",
  "title": "The Mystery Deepens: On the Query Complexity of Tarski Fixed Points"
}