CS Paper Radar

Optimizing Both Checking and Update Costs in Random Walk Search

Simon Apers, Marin Costes

cs.DS cs.CCcs.DMmath.PR ·submitted 2026-09-16 15:41 UTC · v1
theory

Abstract

Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state $m$ and a walk started from its stationary distribution $π$, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix $P$ by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where $τ$ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is \[ S + O(HT(m))U + O(1/π(m))C \] in expectation, where $S$, $U$, and $C$ denote setup, update, and checking costs.

Closest papers

Nearest neighbours by meaning across the whole index.

A proof of Ross's conjecture for two-site moving-target search

cs.DM math.PRmath.OC ·2026-08-10 ·Yunpeng Li
theory similarity 0.64
Abstract

A target moves between two sites according to a discrete-time Markov chain with a $2\times2$ transition matrix $M$. At each epoch one site is searched at positive cost, and a search may overlook a target that is present. Ross conjectured that an optimal policy is threshold in the posterior probability that the target is at site~1. MacPhee and Jordan proved the conjecture throughout the nonpositive-determinant ($\det M\le0$) regime and for part of the positive-determinant ($\det M>0$) regime, leaving the remaining cases open. We prove threshold optimality throughout the positive-determinant regime, completing Ross's conjecture for all parameter values.

0.04

Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch

cs.DS ·2026-09-06 ·Edith Cohen, Elena Gribelyuk, Pasin Manurangsi, Uri Stemmer
similarity 0.62
Abstract

In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyerson sketch opens a facility at each arriving point with probability proportional to the point's distance to the closest open facility, and requires no state beyond the set of open centers. Due to its simplicity, space efficiency, and strong guarantees against the offline optimum, the Meyerson sketch has become a workhorse of streaming and online clustering. In many such applications, however, the set of open facilities are visible to the process that generates the stream, which can adaptively select future points based on the algorithm's past random choices, voiding its classical guarantees. In this work, we quantify the effect of such adaptivity. We compare an adaptively generated run of the sketch against an \emph{oblivious replay}, an independent execution, with fresh coins, on the very same generated sequence, and study the \emph{adaptivity ratio} of expected adaptive cost to expected replay cost. We determine the worst-case ratio in both directions: adaptivity can neither inflate nor deflate the expected cost, or the number of open facilities, by more than an $O(\logΔ/\log\logΔ)$ factor, where $Δ$ is the aspect ratio of the input points (the ratio of the largest to the smallest pairwise distance). This is asymptotically tight as there are deterministic generators on the real line that inflate or deflate the cost by an $Ω(\logΔ/\log\logΔ)$ factor. We show that these robustness guarantees carry over to Meyerson-based sketches for approximate $k$ clustering with sketch size $O(k\,\mathrm{polylog}(n))$.

0.19

Transposition achieves OPT$+O(1)$ in polynomial time for IID list update

cs.DS cs.DM ·2026-09-23 ·Clayton Mizgerd
theory similarity 0.62
Abstract · 11 pages

In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $σ$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

0.45

Improved quantum volume estimation with transducers and amortized quantum walks

cs.CG quant-phcs.DS ·2026-09-30 ·Arjan Cornelissen, Simon Apers, Sander Gribling
similarity 0.60
Abstract

The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential algorithmic techniques related to Markov Chain Monte Carlo and simulated annealing, and the problem connects to several important geometrical results, like the KLS conjecture. In this work, we quantize the state-of-the-art $\widetilde{O}(d^{3.5}+d^3/\varepsilon^2)$-query randomized algorithm developed by Cousins and Vempala, and obtain a $\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$-query quantum algorithm, improving over the $\widetilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ state-of-the-art bound. Our key technical contribution is a framework for amortizing the cost of a quantum walk. The framework is based on the recent transducer toolkit introduced by Belovs, Jeffery and Yolcu. It is this amortized quantum walk framework that allows us to exploit the amortized analysis of the ball walk by Cousins and Vempala, thus overcoming the key barrier that previously barred its quantum implementation.

0.53

Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields

cs.CR ·2026-11-03 ·Mark Braverman, Aayush Jain, Stephen Newman
hot direction similarity 0.60
Abstract

\emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.

0.35

Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF

cs.DS ·2026-11-06 ·Minbo Gao, Kun He, Tao Jiang
similarity 0.58
Abstract

We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

0.33

Optimal and Verifiable Quantum Advantages in Communication Complexity

cs.CC quant-ph ·2026-10-04 ·Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
hot direction similarity 0.58
Abstract · 65 pages

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

0.47

Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

cs.DS quant-phmath.OC ·2026-09-30 ·Guneykan Ozgul, Shouvanik Chakrabarti
similarity 0.58
Abstract

We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.

0.28