Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

Sumegha Garg; Songhua He; Yuanzhi Li; Periklis A. Papakonstantinou; Xin Yang

Source-linked AI summary

Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang

arXiv:2609.18024v1Sep 16, 2026cs.DScs.CC

TL;DR

The paper asks how much probing is necessary for succinct systematic data structures solving AMP and related problems. It introduces a query-with-sketch and min-entropy framework, obtaining probe–redundancy lower bounds for AMP, set intersection, set disjointness, and approximate APSP, while identifying scope limitations.

Problem
The paper studies lower bounds for answering approximate matrix-power queries when the input is stored verbatim and only r additional redundancy bits are available.
Method
It reduces systematic data-structure bounds to query-with-sketch bounds and conditional min-entropy statements, using problem-specific analytic and algebraic techniques.
Results
The framework yields AMP and related probe–redundancy lower bounds, including Ω(n^2/r) average probes for AMP in the stated regimes and Ω(n^2/(r log^3 n)) for set disjointness and approximate APSP.
Takeaways & Limitations
The results provide unconditional evidence toward the Patrascu–Roditty set-disjointness conjecture and establish a new lower-bound barrier for AMP.
Takeaways & Limitations
For general k, the paper gives no matching nontrivial succinct systematic upper bounds, so the AMP result is not a tight characterization.

Abstract

from arXiv · show

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

1 Introduction

The paper develops lower bounds for systematic data structures by reducing query-with-sketch trade-offs to conditional min-entropy, extending the framework to adaptive redundancy updates. Its introduction positions this method against reconstruction-based arguments and states a general amortized probe lower bound.

Systematic data structures store the input verbatim with r=o(N) redundancy and answer queries using bounded probes to the input, while redundancy may be updated afterward.
The framework reduces data-structure lower bounds to query-with-sketch bounds and then to min-entropy conditions on answer vectors after arbitrary partial input assignments.
For a query sequence Q, any succinct and systematic structure with read-write redundancy that answers all queries with at least 99/100 probability requires Ω(N/m) probes per query on average.
The resulting lower bound applies even when the data structure knows the full query sequence and adaptively updates its redundancy after each query.
The introduction connects this line of work to earlier lower bounds for rank, succinct sampling, online matrix-vector multiplication, substring search, prefix sum, and polynomial evaluation.
Unlike reconstruction-based proofs, the approach avoids encoding the input and instead shows that query-block answers retain conditional min-entropy after revealing a small set of input locations.

1.1 Applications to Approximate Matrix Powering

The paper applies its systematic-data-structure framework to AMP and related set and graph problems. It obtains probe–redundancy lower bounds, while noting that general AMP lacks matching nontrivial upper bounds and that the query-with-sketch method has an intrinsic trade-off barrier.

Approximate Matrix Powering: AMP asks for approximations to entries of M^k for substochastic symmetric M, with additive error 1/n^α.
Approximate Matrix Powering: For AMP, the informal overall bound is Ω(n^2/r) probes per query for k=2 and for every k∈[3,n], across the stated redundancy ranges.
Approximate Matrix Powering: The sublinear- and superlinear-in-n redundancy regimes require different hard input distributions and proof techniques, while matrix-square queries can be answered with O(n) probes.
Approximate Matrix Powering: For general k, the paper does not provide matching nontrivial succinct systematic upper bounds, so the AMP result is a barrier rather than a tight characterization.
Set Intersection: Set intersection inherits an Ω(n^2/r) average-probe lower bound under the same parameter regime as the superlinear-in-n AMP result.
Set Disjointness: Set disjointness requires Ω(n^2/(r log^3 n)) average probes in the stated range, providing progress toward the Patrascu–Roditty conjecture in a linear-size universe.
Approximate APSP: The same reduction yields an Ω(n^2/(r log^3 n)) trade-off for (2−ε)-approximate APSP, and this is presented as the first unconditional time-space trade-off for approximate APSP.

1.2 Proof Overview and Technical Contributions

The paper develops a query-with-sketch framework that converts conditional min-entropy into probe lower bounds for systematic data structures, then applies it to AMP and related graph problems.

The query-with-sketch model: The query-with-sketch model captures fixed batches of queries answered using a short sketch and probes to the raw input, supporting reductions from systematic data structures.The framework applies to both single-query and sequential-query variants.
The min-entropy lemma: The min-entropy lemma shows that if answers remain more than r bits uncertain after any q input probes, an r-bit sketch cannot suffice without more than Ω(q) probes on average.The proof views the sketch as selecting one of 2^r decision trees and uses persistent ambiguity at shallow leaves.
The min-entropy lemma: A strengthened version preserves the lower bound when the high-min-entropy condition holds only on a large, high-probability set of good inputs.This strengthening is needed for the paper’s main applications.
Reduction to query-with-sketch: The reduction partitions query sequences into blocks and extracts an r-bit sketch algorithm for one block, transferring systematic data-structure probe bounds to query-with-sketch complexity.The extracted block has a starting index and uses the data structure’s redundancy as its sketch.
Framework limitations: The general method cannot prove trade-offs stronger than r·t=Ω(N log|Y|), reflecting an information-theoretic ceiling of the query-with-sketch reduction.The bound follows because answers themselves can encode the sketch and the input can be fully probed.
Applications to AMP and related problems: The framework yields AMP lower bounds of Ω(n²/r) probes per query, while instantiations use analytic, algebraic, and graph arguments for distinct redundancy regimes.For k=2 the stated range is r∈[Ω(n log n),O(n²)], while for k∈[3,n] it is r∈[Ω(log² n),O(n²)].

2 Query-with-sketch model and the min-entropy lemma

The paper formalizes query-with-sketch algorithms and uses conditional min-entropy to convert uncertainty in outputs into probe lower bounds. This framework reduces systematic data-structure lower bounds to query-with-sketch lower bounds and supports amortized trade-offs.

Query-with-sketch model: The query-with-sketch model gives an algorithm a sketch derived from the input, then permits adaptive probes before producing an output.The sketch is fixed before execution, while probe choices depend on the transcript; repeated probes count with multiplicity.
Query-with-sketch model: A query-with-sketch algorithm is a sketching map plus a deterministic transition rule that chooses probes or halts with an answer.The model also defines randomized algorithms as distributions over deterministic sketch-and-transition pairs.
Min-entropy lemma: The min-entropy lemma lower-bounds probes by showing that output uncertainty persists after conditioning on any short partial assignment to the input.The analysis shifts from information gained by probes given redundancy to entropy loss after arbitrary input elements are revealed without redundancy.
Min-entropy lemma: If conditional joint min-entropy remains above the sketch length, achieving at least 99/100 success requires a sketch longer than the allowed redundancy or many probes.The informal lemma states that min-entropy greater than r under any q-coordinate partial assignment forces more than Ω(q) average probes with an r-bit sketch.
Reduction from data structures: The reduction partitions a query sequence into blocks and represents each block as a query-with-sketch algorithm whose sketch is the data structure’s updated redundancy.The probes and error probabilities are preserved, yielding amortized probe–redundancy lower bounds even when the query sequence is known in advance.
Reduction from data structures: Unlike reconstruction-based arguments, the framework focuses on conditional output min-entropy rather than reconstructing the input from a probe transcript.This separates the lower-bound analysis from the data-structure algorithm itself and connects directly to problem-specific entropy arguments.

3 Lower bounds to approximate matrix powering with sublinearin-n redundancy

For AMP with sublinear-in-n redundancy, the paper proves a strong probe–redundancy lower bound using rounded AMP, structured query blocks, and conditional min-entropy arguments. The resulting data structures require Ω(n^4/r) worst-case probes under the stated redundancy and accuracy conditions.

Main theorem: The proof establishes an r · t = Ω(n^2) trade-off for redundancy below 0.25n ln n, including the sublinear-in-n regime.A subsequent section handles larger redundancy with a different technique, while this section focuses on the stated range.
Main theorem: Ω(n^4/r) worst-case probes are required for AMP with r ∈ (c log^2 n, 0.25n ln n) redundancy and additive error 1/n^α.The theorem applies for 3 ≤ k ≤ n and sufficiently large constant α, with success probability at least 9/10.
Main theorem: Ω(n^2/r) probes are required on average per query, and the same lower bound applies to AMP after the rounded-to-approximate transfer.The transfer loses only o(1) in success probability because boundary inputs occur with probability o(1).
Query construction: The argument uses a fixed sequence of n−1 shifted main diagonals of M^k, partitioned into blocks of consecutive queries.Every window of 3j consecutive queries contains j queries whose row and column indices are all pairwise distinct.
Rounding reduction: Because QwS is designed for exact outputs, the proof first analyzes rounded AMP, where each answer is rounded to precision 1/n^α′.The rounded lower bound transfers to AMP because only boundary inputs, where values lie too close to rounding points, differ between the problems; these inputs have negligible measure.
Min-entropy analysis: For each query block, conditional min-entropy is lower-bounded after fixing q = 10^-4n^2 matrix entries, enabling the query-with-sketch reduction.The construction uses a nontrivial good-matrix set and applies the min-entropy lemma to force either sufficient sketch length or Ω(n^2) block probes.
Min-entropy analysis: The Jacobian of selected matrix-power entries has large singular values even under small additive perturbations, supporting the high-min-entropy bound.For pairwise-distinct input and output indices, the singular-value lower bound holds with probability at least 1−exp(−Ω(m)) and remains valid under O(k^5/n^(2+3β)) perturbations.

4 Lower bounds to approximate matrix powering with superlinearin-n redundancy

This section proves an AMP probe lower bound for superlinear redundancy by combining a three-layer matrix distribution with conditional min-entropy arguments. The resulting trade-off is also inherited by counting set intersection.

Input distribution: The nemesis distribution uses a three-layer symmetric graph with independent probability-1/2 edges between consecutive layers and heavy lazy transitions.Only the V1×V2 and V2×V3 submatrices vary; all other matrix entries are fixed.
Reduction to path counting: Approximating M^k entries between V1 and V3 exactly recovers the number, and hence parity, of length-2 paths for every 2 ≤ k ≤ n.The path count equals a neighbor-set intersection size, reducing the matrix problem to a combinatorial task.
Query construction: The query sequence concatenates disjoint bijections between V1 and V3, while consecutive blocks distribute queries so no index is covered too often.This structure supports the construction of many edge-disjoint triples whose unrevealed entries contribute independent output uncertainty.
Min-entropy analysis: Random inputs are good with high probability because every relevant d×d binary submatrix has rank at least d/2 with probability 1-o(1).The rank property supplies a basis for output parities and yields at least d/2 min-entropy per sufficiently queried vertex; distinct output columns then add their contributions.
4 Lower bounds to approximate matrix powering with superlinearin-n redundancy: Ω(n4/r) total probes are required for AMP when r ∈ [10n log n, n2/1000] and α > 6.The bound applies to succinct and systematic data structures answering the whole approximated matrix power with probability at least 99/100.
Consequence: The same Ω(n4/r) probe lower bound holds for counting set intersection over the stated superlinear redundancy range.The distribution and analysis therefore apply beyond AMP’s matrix formulation.

5 Lower bounds to set disjointness and (2 −ε)-approximate APSP

This section extends the min-entropy framework to set disjointness using sparse-set inputs, then transfers the resulting lower bound to approximate APSP. The key bounds are Ω(n4/(r log3 n)) probes in the stated redundancy ranges.

Nemesis distribution: The set-disjointness construction uses sparse random sets, with each membership bit equal to 1 independently with probability 1/(√n log n).Under this distribution, each nonidentical pair has a NO answer with probability Θ(1/log2 n).
Set disjointness lower bound: Ω(n4/(r log3 n)) worst-case probes are required for set disjointness with r ∈ [10n log2 n, n√n/(1000 log3 n)].The bound applies to succinct and systematic data structures answering the query sequence correctly with probability at least 99/100.
Min-entropy analysis: The answers cannot be treated as nearly linear combinations of selected input elements, so sparsity rather than algebraic structure supplies the min-entropy lower bound.This motivates the separate good-input construction used for set disjointness.
Min-entropy preparation: Good inputs preserve conditional uncertainty after partial assignments by controlling set sizes, shifted-bijection overlaps, and local membership counts.Random inputs satisfy the good-input conditions with probability at least 99/100, while the refined sets Aσ retain uncertainty in unprobed bits.
Approximate APSP: The same Ω(n4/(r log3 n)) worst-case probe bound applies to (2−ε)-approximate APSP for r ∈ [5n log2 n, n√n/(4000 log3 n)].The reduction constructs a graph where distance 2 corresponds to intersecting sets, while disjoint pairs have distance at least 4.

A Missing proof to Lemma 3.5

This appendix fills in the proof of Lemma 3.5 by controlling how each matrix-power entry varies with one underlying matrix element. It then bounds the probability that an entry lies near any discretization center.

A Missing proof to Lemma 3.5: The proof studies each M^k[u,v] as a function of one unfixed symmetric entry after all other entries are partially assigned.A union bound over all indices completes the high-probability statement once each fixed entry is controlled.
Derivative bounds: Partial derivatives are largest when the input and output index pairs coincide, smaller when exactly one endpoint coincides, and smallest otherwise.The corresponding bounds are Θ(k), Θ(k2/n^(1+β)), and Θ(k3/n^(1+2β)).
Discretization argument: The range of M^k[u,v] has length Θ(k/n^(γ+β)), producing Θ(k n^(α′−γ−β)) approximation discs.Each disc corresponds to an input interval of length at most Θ(n^β/(k n^α)).
Conclusion: The union-bound failure probability is o(1) when α > 2 + α′.This condition makes the total input volume mapping into the relevant approximation discs vanish asymptotically.

B Missing proof to Lemma 3.13

This appendix proves Lemma 3.13 by showing that the relevant entry distributions have bounded density and constant subgaussian parameters. A random-matrix singular-value theorem then yields constant comparison bounds.

B Missing proof to Lemma 3.13: Lemma 3.13 is obtained by applying an intermediate-singular-value concentration theorem to the random matrix A.The required constants depend only on the distribution parameters and remain bounded in the two cases considered.
Underlying distributions: The two distributions are a four-fold sum of uniform variables and a sum of two independent products of uniform variables, each scaled to have variance 1.The proof verifies constant parameters p and K for both distributions.
Subgaussian parameters: Both distributions have constant subgaussian norm because their variables are supported on constant-bounded intervals.Thus K = Θ(1) follows directly from boundedness.
Density bounds: The four-fold sum has bounded density because repeated applications of Young’s convolution inequality preserve an L∞ bound.The argument explicitly uses that the uniform density has unit L1 norm.
Product-sum distribution: The product-sum distribution is handled by a change of variables for each product followed by convolution of the two independent product distributions.This establishes the bounded-density condition needed by the singular-value result.

C Lower bound to set disjointness for a full range of redundancy

The appendix proves a set-disjointness probe lower bound across a broad redundancy range using repeated shifted-bijection queries and a min-entropy argument. It also transfers the bound to approximate APSP.

Hard distribution: A random input distribution independently sets each set element to 1 with probability 1 − 2^(-1/d), and good inputs contain many zero intersection answers.Good inputs occur with probability at least 99/100.
Query construction: The proof uses n/2 shifted bijections between two vertex groups, with repeated sets in the second group producing Θ(n^2/r) complete query blocks.Each block contains the same cross-group answers up to ordering and repetitions.
Lower bound: For redundancy r ∈ [n, n^2/1024], set-disjointness queries require Ω(n^4/r) total probes, equivalently Ω(n^2/r) probes per query.The result applies to succinct and systematic structures answering the query sequence with probability at least 99/100.
Min-entropy argument: Conditioned on any short partial assignment, a block answer vector forces many unrevealed input bits to zero, yielding conditional min-entropy above the redundancy threshold.The argument applies the query-with-sketch lemma to show that each complete block requires Ω(n^2) probes on average.
Range limitation: The upper redundancy endpoint must remain below a small constant multiple of n^2 because storing all n^2/4 query answers eliminates input probes.Thus the stated range excludes the regime where redundancy can explicitly contain the entire answer sequence.
APSP consequence: The lower bound transfers to (2 − ε)-approximate APSP by encoding set intersections as graph distances, preserving redundancy, probes, and success probability.Distance 2 corresponds to a nonempty intersection, whereas disjoint pairs have distance at least 4.