Abstract:Consider 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 $\Omega(n)$, which technically implies a linear setup time. Any blackbox derandomization would likely need $\Omega(\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 $\omega_N(1)$ random bits.
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2605.23509 [cs.DS] |
| (or arXiv:2605.23509v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23509 arXiv-issued DOI via DataCite (pending registration) |
From: Abhiruk Lahiri [view email]
[v1]
Fri, 22 May 2026 11:17:08 UTC (30 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。