CS Paper Radar

Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan

cs.IT cs.DScs.LG ·submitted 2026-10-17 22:12 UTC · v1
theory

Abstract

We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.

Comment
66 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

cs.IT stat.MLcs.LGmath.ST ·2026-09-08 ·Ivan Lau, Jonathan Scarlett
similarity 0.67
Abstract

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query $Q: \mathbb{R}\to\{0,1\}$ chosen by a central learner. The distribution has mean in $[-λ,λ]$ and $k$-th central moment at most $σ^k$, for a fixed $k>1$. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set $Q^{-1}(1)$ is restricted to a union of at most $s$ intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order $(λσ/(s\varepsilon^2))\log(1/δ)$, giving the full tradeoff between sample complexity and interval complexity to within $k$-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.

0.22

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

cs.DS quant-ph ·2026-10-05 ·Nadezhda Voronova
theory similarity 0.64
Abstract

How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.

0.27

Optimal compression with quantum retrieval

cs.DS quant-phcs.IRcs.IT ·2026-10-05 ·Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan
similarity 0.63
Abstract · 13 pages, 3 figures

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

0.12

Quantization Beyond Uniform Bit Allocation

cs.IR cs.DB ·2026-08-19 ·K. S. Sreeramji, Sabyasachi Basu, Ravishankar Krishnaswamy, Kirankumar Shiragur, Yujia Wang
published similarity 0.63
Abstract · Accepted at the 2nd Workshop on Vector Databases (VecDB), part of 52nd International Conference on Very Large Data Bases (VLDB 2026)

Quantization is a fundamental technique to handle the growing sizes of embeddings generated by modern models. Existing quantization schemes are largely embedding agnostic and allocate bits uniformly across dimensions. However, recent models produce embeddings with significant geometric structure. In this work, we investigate whether a variable bit allocation scheme can improve quantization quality under a fixed memory budget. We propose a simple variable bit allocation framework that partitions an embedding into contiguous buckets and allocates storage non-uniformly across them. Using a greedy allocation strategy, we instantiate this framework for both Product Quantization (PQ) and Scalar Quantization (SQ). We perform a series of experiments on embeddings known to have the Matryoshka property (MRL), and consistently observe that non-uniform allocations outperform uniform baselines at identical storage budgets. The largest improvements occur in the low-bit regime, where uniform allocation is particularly inefficient for MRL embeddings. At the same compression rates, variable allocation improves recall by up to 8\% for PQ and up to 18\% for SQ. Our results suggest a new direction for structure-aware compression and indexing techniques for large-scale retrieval systems.

0.25

Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries

cs.DS ·2026-08-18 ·Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari
publishedtheoryhot direction similarity 0.63
Abstract · Accepted at SPIRE 2026. Full version

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $σ$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $σ= 2,3,4,5$, and approximately $n\sqrt{π/(2σ)}\,\logσ$ bits for $σ=ω(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $σ$, and $O(1)$ expected time for any $σ= ω(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $Ω(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.

0.39

Exponential quantum space advantage in random data streams

cs.CC quant-ph ·2026-10-02 ·Adam Bouland, Matthew Ding, Siddhartha Jain
theory similarity 0.63
Abstract · 27+3 pages. v2: fixed minor typos and added concurrent work statement

We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa-Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Notably, our classical space lower bound does not follow from a communication lower bound. Instead, we utilize density-restoring partitions from communication complexity directly with potential-function analysis in the style used to prove memory-sample tradeoffs for learning. The resulting argument is distinct from both lines of work. Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm. In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.

0.48

Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator

cs.CC cs.IT ·2026-11-03 ·Guy Goldberg, Tom Gur, Sidhant Saraogi
theory similarity 0.62
Abstract

We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.

0.22

Cache-Aided Linear Function Computation

cs.IT ·2026-10-14 ·Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
theory similarity 0.62
Abstract · 11 pages, 2 figures. A shorter version has been submitted to the 2027 IEEE Information Theory Workshop (ITW)

We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the $N$ sources stores its own independent file over a finite field and has an additional cache of normalized size $M$. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every $N\geq3$, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for $0\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.

0.22