2026-07-23T20:56:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27083 2026-07-23T11:36:20Z ddc:004 open_access

Systematic Data Structure Lower Bounds via the Query-With-Sketch Model Garg, Sumegha He, Songhua Li, Yuanzhi Papakonstantinou, Periklis A. Yang, Xin systematic data structure query-with-sketch model approximate matrix powering 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumegha Garg and Songhua He and Yuanzhi Li and Periklis A. Papakonstantinou and Xin Yang 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.41 urn:nbn:de:0030-drops-270833 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.41 eng https://creativecommons.org/licenses/by/4.0/legalcode