DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.41

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

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

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix 𝐌 ∈ ℝ^{n× n} and parameters k and α, the goal is to preprocess 𝐌 so as to answer entry queries (u,v)↦ 𝐌^{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 𝐌 verbatim, uses an additional r bits of redundancy, and must answer queries by probing only a small number of entries of 𝐌. 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 Pătraşcu and Roditty on the space required for constant-time set-disjointness queries [Patrascu and Roditty, 2010].

Cite as

Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, and Xin Yang. Systematic Data Structure Lower Bounds via the Query-With-Sketch Model. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 41:1-41:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2026.41,
  author =	{Garg, Sumegha and He, Songhua and Li, Yuanzhi and Papakonstantinou, Periklis A. and Yang, Xin},
  title =	{{Systematic Data Structure Lower Bounds via the Query-With-Sketch Model}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{41:1--41:44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.41},
  URN =		{urn:nbn:de:0030-drops-270833},
  doi =		{10.4230/LIPIcs.CCC.2026.41},
  annote =	{Keywords: systematic data structure, query-with-sketch model, approximate matrix powering}
}

Search Results

Documents authored by Li, Yuanzhi

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

Abstract

Cite as

Thanks for your feedback!

Could not send message