CS Paper Radar

A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution

Trevor Vaughn

cs.DS ·submitted 2026-08-17 05:28 UTC · v1

Abstract

Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{supp}(A \star B)|$. We give a Las Vegas algorithm that computes $A \star B$ in $O(t \log t)$ expected time. More generally, for every $0 < δ\le \frac{1}{2}$, the algorithm terminates within $O(t \log t \log \frac{1}δ)$ time with probability at least $1 - δ$. The algorithm uses dense convolution, linear hashing, and the length reduction of \cite{BFN22}. Its main ingredient is a carry-free representation of the indices as vectors of constant dimension $d$ whose coordinates have size $O(t / \log t)$. We can then take our hash function to be the inner product with a random element of $\mathbb{F}_p^d$ for a prime $p$ of size $Ω(t / \log t)$: this preserves addition and gives collision probability exactly $1/p$, while identities regarding the moments of the vectors identify and recover the isolated terms as in \cite{BFN22}. Our expected running time matches that of Jin and Xu~\cite{JX24} while using substantially different tools and yielding a simpler algorithm. Note that their algorithm also terminates within $O(t \log t)$ time with probability at least $1 - \frac{1}{t}$, while our tail bound is weaker.

Closest papers

Nearest neighbours by meaning across the whole index.

Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering

cs.DS cs.DB ·2026-10-07 ·Mihail Stoian
hot direction similarity 0.69
Abstract · Feedback welcome; v2: fixed technique naming

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

0.27

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.63
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

cs.IT cs.CCcs.DSmath.CO+1 ·2026-09-15 ·Vinayak M. Kumar, Geoffrey Mon
publishedtheoryhighly cited similarity 0.62
Abstract

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

0.43

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

cs.CC ·2026-11-10 ·Dhruv Prasad Deshpande, Abhishek Mishra
similarity 0.61
Abstract · 21 pages

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

0.17

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.60
Abstract

We show that an $\widetilde{O}(m^ρ)$-time algorithm for integer $(\min,+)$-convolution, where $1<ρ<2$, gives a randomized fully polynomial-time approximation scheme for $0$--$1$ Knapsack running in $\widetilde{O}(n+(1/ε)^{1+ρ/2})$ time. The algorithm returns a feasible solution whose profit is at least the optimum divided by $1+ε$, with high probability. We use the all-capacities proximity decomposition of Chen, Lian, Mao, and Zhang. Its two quadratic computations are replaced by blocked computation of requested prefix and suffix functions, and exact computation within groups sharing one of Chan's profit grids. Thus the approximation scheme retains half of the saving in the convolution exponent. Wang's weighted-cache 3SUM bound, transferred to witnessed integer convolution by Zhou, gives the numerical bound $\widetilde{O}(n+(1/ε)^{1.981})$.

0.26

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

cs.DS ·2026-11-03 ·Alex Conway, Hanna Komlós, William Kuszmaul
similarity 0.59
Abstract

A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|x|)$ for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.

0.21

Improved Quantum Random Self-Reduction for Linear Problems

cs.CC quant-ph ·2026-09-30 ·Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
similarity 0.58
Abstract

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2/3$ in time $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.

0.47

The threshold for online balancing of i.i.d. binary vectors

cs.DS math.PRmath.CO ·2026-09-14 ·Dylan J. Altschuler, Konstantin Tikhomirov
theory similarity 0.58
Abstract · Supersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.

0.44