{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigtmcwpbudfwd55zwp7p7n3kckvfqnjbqcbw2n6e366xc5jgp3eei",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmnyr4r7oam2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.23509v1",
  "publishedAt": "2026-05-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Akash Kumar",
    "Abhiruk Lahiri",
    "C. Seshadhri"
  ],
  "textContent": "**Authors:** Akash Kumar, Abhiruk Lahiri, C. Seshadhri\n\nConsider a bounded-degree graph $G$ that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $\\varepsilon > 0$, one can remove $\\varepsilon dn$ edges to obtain connected components of size independent of $n$. (As usual, $n$ is the number of vertices and $d$ is the degree bound.) In a seminal result, Hassidim-Kelner-Nguyen-Onak (FOCS 2009) introduced the partition oracle, a procedure that provides local access to a hyperfinite decomposition. The partition oracle computes the component containing an input vertex $v$ with query complexity (to $G$) independent of $n$. Remarkably, this is done without any preprocessing on $G$. The coordination is done purely through a shared random seed. Despite a line of work on optimizing the query complexity of partition oracles, there were no attempts to bound the size of the random seed. All existing partition oracles use a random seed of size $Ω(n)$, which technically implies a linear setup time. Any blackbox derandomization would likely need $Ω(\\log^2n)$ uniform random bits. A natural question is whether the random seed can also have length independent of $n$. We prove the $poly(d\\varepsilon^{-1})$-query partition oracles of Kumar-Seshadhri-Stolman can be implemented with a random seed of $poly(d\\varepsilon^{-1}) \\cdot \\log n$ length. To get a deeper understanding on the randomness complexity, we consider a more general model where the vertex labels come from the universe $[N]$, where $N \\geq n$. In this setting, we prove that any partition oracle even for cycles requires $ω_N(1)$ random bits.",
  "title": "Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs"
}