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}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.67

Query Lower Bounds for Correlation Clustering Under Memory Constraints

Authors: Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

This work initiates the study of memory–query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non‑edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of ε n², any algorithm requires Ω(n/ε²) adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make ≫ n/ε² adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.

Cite as

Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou. Query Lower Bounds for Correlation Clustering Under Memory Constraints. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2026.67,
  author =	{Garg, Sumegha and He, Songhua and Papakonstantinou, Periklis A.},
  title =	{{Query Lower Bounds for Correlation Clustering Under Memory Constraints}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{67:1--67:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.67},
  URN =		{urn:nbn:de:0030-drops-253542},
  doi =		{10.4230/LIPIcs.ITCS.2026.67},
  annote =	{Keywords: correlation clustering, query-space complexity, information theory}
}

Search Results

Documents authored by He, Songhua

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

Abstract

Cite as

Query Lower Bounds for Correlation Clustering Under Memory Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message