CS Paper Radar

Optimal (Parallel) Spooky Pebbling on Binary Trees

Mingyu Lee, Sanghyun Lee, Kabgyun Jeong

cs.CC ·submitted 2026-10-07 04:43 UTC · v1

Abstract

Pebble games model computations under a fixed space budget. Spooky pebbling allows quantum memory to be released by measurement, with the resulting phases corrected later. We study two-input computations with binary-tree dependencies and determine the optimal work and parallel depth for complete binary trees. Our key idea is to clean up the tree in blocks, reducing repeated recomputation of intermediate values. For the complete tree $B_h$ with $n=2^h-1$ vertices and every space budget $h+1\le s\le n$, we give an algorithm with asymptotically optimal work $Θ(nh/\log(s+1))$. At the minimum budget $s=h+1$, this improves the $O(n\log n)$ bound of Kornerup, Sadun, and Soloveichik to $Θ(n\log n/\log\log n)$, resolving their time-optimality question. We also construct a parallel schedule with optimal depth \[ Θ\!\left(h+\frac ns \max\!\left\{\frac{h}{\log(s+1)},\,1+\log^*h\right\}\right). \] Our lower bounds hold for every full binary tree. We also show that achieving optimal parallel depth can require asymptotically more work than minimizing work alone. Applying our schedule to the RNS point-addition trees in the public implementation of Chevignard, Fouque, and Schrottenloher reduces their Toffoli/AND gate count by $20.86\%$ for a P-224 instance and $22.66\%$ for a P-256 instance, using the same arithmetic circuits and peak workspace.

Comment
21 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

cs.DS cs.CCquant-ph ·2026-11-09 ·Sebastian Senge
code/data similarity 0.63
Abstract · 18 pages, 4 tables. Lean 4 formalization and scripts: https://github.com/ssenge/LAIF

We give quantum algorithms for exponential-time problems on $n$ vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time $O(1.3032^n)$, from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, $O(1.3100^n)$. The previous best bound in this model, to our knowledge, is $O(1.3231^n)$. (2) $k$-Colouring below the previous best bound for $k \in \{5, 7, 8, 9, 10, 11\}$ and $13 \le k \le 18$, from $O(1.4518^n)$ for $k = 5$ to $O(1.9233^n)$ for $k = 18$. (3) Dominating Set in $O(1.2235^n)$, against the previous $O(2^{n/2})$, Independent Dominating Set in $O(1.1583^n)$, and Edge Dominating Set and Minimum Maximal Matching in $O(1.1501^n)$. (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with $c^k$ nodes up to polynomial factors, the problem is solved in quantum time $(2 - 1/c)^{n/2}$ up to polynomial factors. This gives Feedback Vertex Set in $O(1.3081^n)$, Subset and Group Feedback Vertex Set in $O(1.3229^n)$, Cluster Vertex Deletion in $O(1.2033^n)$, 3-Hitting Set in $O(1.2405^n)$, Proper Interval Vertex Deletion in $O(1.3541^n)$, Multicut on Trees in $O(1.1647^n)$ and Min-Ones $d$-SAT in $O^*((2-1/d)^{n/2})$. (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in $O(1.0555^n)$ and for Feedback Vertex Set in $O(1.2161^n)$. The colouring exponents for $k \ge 6$ come from an evaluation of a known reduction recursion, computed in floating point with a margin.

0.44

Solving Streett and Emerson-Lei Games with Universal Trees

cs.GT cs.LO ·2026-08-17 ·Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
similarity 0.63
Abstract

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

0.18

Sharper Bounds for Graphical Two-Choice Allocation

cs.DS math.PR ·2026-11-01 ·Obinna Okechukwu
benchmarktheory similarity 0.63
Abstract · 28 pages, 5 figures

In graphical two-choice allocation, vertices are bins, and each arriving ball must be placed irrevocably at one endpoint of a uniformly random edge. The objective is to keep the maximum-minus-minimum load gap small at every time. On cycles, endpoint-local monotone rules incur polynomial gaps at long time horizons, whereas global rules can achieve polylogarithmic gaps. We prove a joint exponential-moment inequality for the orthogonal contrasts of a binary partition tree, controlling all contrasts along a root-to-leaf path simultaneously. Applied to the Bansal--Feldheim strategy, it improves the gap on every $κ$-edge-connected $d$-regular graph from $O((d/κ)\log^4 n\log\log n)$ to $O((d/κ)\log^3 n\log\log n)$. We give an explicit strategy on the $n$-cycle with expected gap $O(\log^2 n)$ uniformly over deterministic times and exponential tails at each such time. An Euler-tour projection yields $O(\bar d\log^2(2M))$ for every connected graph with $M$ edges and degree-proportional capacities. For lower bounds, we introduce a stochastic cut workload: the expected largest normalized overload forced by the requests, plus an indivisibility term. For every online integral strategy, the supremum over time of the expected gap is at least one sixth of this benchmark. Regular rings of cliques attain $Ω((d/κ)\log n)$ along an explicit family, improving the prior additive lower bound. With unequal capacities, the workload need not control the gap: one family has constant relative cut slack, bounded workload and gap $Ω(\log\log n)$; another has workload at most $20$ but forces gap $Ω(\log n)$ even for clairvoyant fractional allocations that remain irrevocable.

0.22

Collective Tree Exploration with Predictions

cs.DS cs.MA ·2026-11-12 ·Romain Cosson, Yichen Huang, Michael Mitzenmacher, Ali Vakilian
benchmark similarity 0.61
Abstract

We study collective tree exploration with subtree-size predictions. In this problem, a team of $k$ mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex $u$ is discovered, the team receives a prediction $\hat n_u$ of the number of nodes $n_u$ in the subtree rooted at $u$. We provide algorithmic guarantees under two error measures: the maximum error $E=\max_u|\widehat n_u-n_u|$ and the multiplicative distortion $μ= (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u)$. For the maximum error, we present a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in $O(\text{OPT}+E)$ rounds, where $\text{OPT} = Θ(n/k+D)$ is the offline benchmark, and we show that there is no deterministic algorithm that admits an $O(\text{OPT})+o(E)$ guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in $\widetilde O(\min\{ \sqrtμ\log k, μ\log\log k+μ^{1.5} \})$, where the $\widetilde O(\cdot)$ may hide logarithmic factors in $μ$.

0.17

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.61
Abstract · 20 pages

We prove the first unconditional amortized $Ω\big((\log N/\log\log N)^2\big)$ cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with $N$ query sets over $[N]$ and word size $w=Θ(\log N)$, a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove $t_q=Ω\big((\log N/\log(t_uw))^2\big)$ for amortized insertion time $1\le t_u=N^{o(1)}$ and expected query time $t_q$, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simulations.

0.27

Prefix Sharing Is a Sorting Problem

cs.DS cs.CL ·2026-09-12 ·Rong He
theorycode/data similarity 0.60
Abstract · 16 pages. v2: Corrected the spanning-tree lower-bound implementation and retrieval summary statistics; clarified the scope of empirical opti…

LLM serving reuses KV cache by exact prefix match, so when a prompt is assembled from a set of reusable pieces -- retrieved passages, tool definitions, few-shot exemplars -- the order chosen for those pieces determines how much computation can be shared. Every deployed system fixes that order by a single global convention. We prove this is optimal only when requests contain at most two pieces, and asymptotically wrong in general. Our main result is a structure theorem: the minimum prefix-trie cost equals min_H sum_x w(x) t_x(H) over binary hierarchies H on the requests, where t_x(H) is the canonical decomposition size of the set of requests needing chunk x. Choosing chunk orders is therefore equivalent to choosing one hierarchy over requests. The identity yields an O(3^m) exact algorithm, identifies the two-chunk case as minimum vertex cover, and shows that on the leave-one-out family the optimum is the minimum external path length of a binary tree -- the merge-sort recursion -- so a global order pays Theta(n^2) against a true cost of Theta(n log n). Agglomerative clustering by common intersection is a tight 1/2-approximation for the achievable saving. On BM25 retrieval traces over three BEIR corpora the resulting layout reduces prefill by 17-36% against production RAG ordering, and the margin widens with retrieval depth as the theory predicts. Serving requests in the hierarchy's DFS order finally lets a cache holding one request's context attain the unbounded-cache optimum exactly, so cache capacity and reorder window act as substitutes.

0.28

Dynamically optimal weight-balanced binary search trees

cs.DS ·2026-10-21 ·John Iacono, Akash Pareek
similarity 0.60
Abstract

In STOC 1972, J{ü}rg Nievergelt and Edward M.~Reingold introduced the $BB[α]$-tree, also known as a \emph{weight-balanced} tree, which for any $α\in (0,\frac{1}{2}]$ is a binary search tree where every node with induced subtree size $s$ has children with induced subtree sizes at least $α(s+1)-1$. A new rotation-based binary search tree, the \emph{PopTree}, is introduced. The PopTree stores $n$ elements and is a $BB[\tfrac1{20}]$-tree after the execution of each search and a $BB[\tfrac1{729}]$-tree at all times, notably while rebalancing. For any constant $α$, its performance on search sequences of length $Ω(n \log n)$ is proved to be within a constant factor (which can depend on $α$) of the optimal offline rotation-based binary search tree that maintains the $BB[α]$ balance invariant.

0.23

Differentially Oblivious Priority Queues with Sublogarithmic Cost

cs.DS cs.CC ·2026-11-03 ·Zimai Guo, Cheng Hong, Zhechen Li
theoryhot direction similarity 0.60
Abstract · 38 pages, 1 figure

In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.

0.36