Pith. sign in

REVIEW 2 minor 25 references

The intersection profile of a distribution over subsets requires Ω(n²) bits to sketch to constant additive error.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-27 05:13 UTC pith:CQZ3SAGO

load-bearing objection The paper settles three sketching lower bounds at Ω(n²) via an elementary proof for intersection profiles.

arxiv 2606.13182 v1 pith:CQZ3SAGO submitted 2026-06-11 cs.DS cs.CC

Sketching Intersection Profiles: A Simple Proof and Three Applications

Flavio Chierichetti , Mirko Giacchini , Ravi Kumar , Alessandro Panconesi , Erasmo Tani , Andrew Tomkins This is my paper
classification cs.DS cs.CC
keywords sketchingintersection profilelower boundsgraph neighborhoodscoverage functionsrandom utility modelsitemset frequency estimation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that approximating, for any query set S, the probability that a random set T intersects S requires Ω(n²) bits when the approximation is to constant additive error. This sketching problem is connected directly to itemset frequency estimation, allowing the known lower bound to carry over. The authors supply a new elementary proof of the lower bound that uses only basic probability. Applying the result gives Ω(n²) lower bounds for sketching vertex neighborhood sizes in graphs, coverage functions under additive or multiplicative error, and random utility models under the ℓ∞ norm. These stand in contrast to the linear-space sketching possible for edge cuts.

Core claim

Sketching the intersection profile of a distribution D on 2^[n] requires Ω(n²) bits to approximate Pr[T ∩ S ≠ ∅] to within constant additive error for every query S. This directly yields Ω(n²) lower bounds for vertex neighborhood sketching, coverage function sketching, and ℓ∞ sketching of random utility models. An alternative elementary probability proof is given for the intersection profile lower bound.

What carries the argument

The intersection profile sketching problem: a succinct data structure that approximates Pr_{T ~ D}[T ∩ S ≠ ∅] to small constant additive error for any query S ⊆ [n].

Load-bearing premise

The known Ω(n²) lower bound for itemset frequency estimation translates directly to the constant-additive-error intersection-profile sketching problem without extra assumptions on the distribution.

What would settle it

Finding a sketching data structure that uses o(n²) bits while approximating the intersection probability to constant additive error for all queries would falsify the claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Sketching vertex neighborhood sizes in graphs requires Ω(n²) bits, unlike the Õ(n) for edge cuts.
  • Sketching coverage functions requires tight Θ̃(n²) bits for both additive and multiplicative errors.
  • Sketching random utility models under the ℓ∞-norm requires Ω(n²) bits, improving the previous Ω(n log n) bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The simple elementary proof may allow easier extensions of constant-error lower bounds to related problems.
  • The quadratic space requirement separates intersection-based sketching from simpler linear-space graph problems like edge cuts.
  • These bounds suggest that database-style frequency problems underlie the hardness of several set-query sketching tasks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript claims to settle the sketching complexity of three problems by reducing them to sketching the intersection profile Pr[T ∩ S ≠ ∅] (constant additive error) of a distribution D on 2^[n]: it proves Ω(n²) lower bounds for (i) vertex neighborhood sketching in graphs (contrasting with Õ(n) edge-cut sketching), (ii) coverage-function sketching (tight ãΘ(n²) for additive/multiplicative error), and (iii) ℓ_∞ sketching of random utility models (improving prior Ω(n log n) to match known upper bounds up to logs). Lower bounds follow from itemset frequency estimation, but the paper supplies an independent elementary-probability proof of the Ω(n²) intersection-profile lower bound that avoids database machinery.

Significance. If the central claims hold, the work supplies tight, load-bearing lower bounds that cleanly separate the complexity of these sketching tasks from related problems such as edge-cut sketching. The provision of an independent elementary proof (distinct from the itemset-frequency reduction) is a concrete strength: it renders the lower bound self-contained within basic probability and directly addresses the reduction assumption flagged in the reader report. No machine-checked proofs or reproducible code are mentioned, but the falsifiable Ω(n²) predictions and parameter-free nature of the elementary argument add value.

minor comments (2)
  1. [Abstract] Abstract, paragraph beginning 'One can obtain lower bounds...': the sentence introducing the elementary proof does not name the section in which the argument appears, making it harder for readers to locate the self-contained proof.
  2. The manuscript does not explicitly compare the new elementary proof's assumptions or error regime to the database reduction (e.g., whether the elementary argument also works for non-constant accuracy parameters).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment, accurate summary of the contributions, and recommendation to accept. We are pleased that the elementary proof and the separation from related sketching problems were viewed as strengths.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper connects its three sketching lower bounds to the intersection-profile sketching problem and notes that Ω(n²) bounds follow directly from known itemset-frequency results; however, it supplies a fully independent elementary-probability proof of the same Ω(n²) lower bound for constant additive error that relies on no external results, no self-citations, and no fitted parameters. Because this self-contained proof bears the central claim, the derivation chain contains no self-definitional, fitted-input, or self-citation reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard axioms of probability and on the known itemset-frequency lower bound; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard axioms of probability (expectation, union bound, etc.)
    Invoked in the elementary proof of the intersection-profile lower bound.

pith-pipeline@v0.9.1-grok · 5804 in / 1234 out tokens · 29861 ms · 2026-06-27T05:13:10.487008+00:00 · methodology

0 comments
read the original abstract

In this work we settle the complexity of three sketching problems. (i) We show that sketching vertex neighborhood sizes in graphs requires $\Omega(n^2)$ bits, standing in sharp contrast to the $\tilde{O}(n)$ complexity of sketching edge cuts. (ii) We obtain tight lower and upper bounds of $\tilde{\Theta}(n^2)$ for sketching coverage functions with additive and multiplicative errors. (iii) We prove an $\Omega(n^2)$ lower bound for sketching Random Utility Models under the $\ell_\infty$-norm, improving upon the previous $\Omega(n \log n)$ bound and matching a known upper bound to within logarithmic factors. These bounds are obtained through a connection with the problem of sketching the intersection profile of a distribution $D$ on $2^{[n]}$. Specifically, we seek a succinct data structure that, for any query set $S \subseteq [n]$, approximates the quantity $\Pr_{T \sim D}[T \cap S \neq \varnothing]$ to within a small constant additive error. One can obtain lower bounds for this latter problem directly from known results about the itemset frequency estimation problem in databases for which tight bounds are known. As an additional contribution, we also provide an alternative proof for the intersection profile sketching lower bound, in the setting in which the accuracy parameter is constant. This proof relies solely on elementary probability avoiding the heavier machinery used in previous proofs.

Figures

Figures reproduced from arXiv: 2606.13182 by Alessandro Panconesi, Andrew Tomkins, Erasmo Tani, Flavio Chierichetti, Mirko Giacchini, Ravi Kumar.

Figure 1
Figure 1. Figure 1: First, the m × n matrix [M | Im] with Mi,j ∼ Bernoulli(1/2). Each row i of this matrix is the indicator vector of the set S (M) i . The power-set distribution DM associated with the matrix M selects a subset by sampling a row of this matrix uniformly at random, and interpreting the row as the indicator of the corresponding subset of [n] = [2m]. Below that, the matrix [Im|11⊤ − M⊤]. Each row j of this matri… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references

  1. [1]

    Spectral sparsification and regret minimization beyond matrix multiplicative updates

    Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In STOC, pages 237--245, 2015

    2015

  2. [2]

    Learning with submodular functions: A convex optimization perspective

    Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning , 6 0 (2-3): 0 145--373, 2013

    2013

  3. [3]

    Sketching valuation functions

    Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In SODA, pages 1025--1035, 2012

    2012

  4. [4]

    Maria-Florina Balcan and Nicholas J. A. Harvey. Submodular functions: Learnability, structure, and optimization. SICOMP, 47 0 (3): 0 703--754, 2018

    2018

  5. [5]

    Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In RANDOM, pages 1--10, 2002

    2002

  6. [6]

    Almost optimal streaming algorithms for coverage problems

    MohammadHossein Bateni, Hossein Esfandiari, and Vahab Mirrokni. Almost optimal streaming algorithms for coverage problems. In SPAA, 2017

    2017

  7. [7]

    Spielman, and Nikhil Srivastava

    Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice- R amanujan sparsifiers. SICOMP, 41 0 (6): 0 1704--1721, 2012

    2012

  8. [8]

    Approximating st minimum cuts in O (n^2) time

    Andr \'a s A Bencz \'u r and David R Karger. Approximating st minimum cuts in O (n^2) time. In STOC, pages 47--55, 1996

    1996

  9. [9]

    Optimal lower bounds for sketching graph cuts

    Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. Optimal lower bounds for sketching graph cuts. In SODA, pages 2565--2569, 2019

    2019

  10. [10]

    Recognizing coverage functions

    Deeparnab Chakrabarty and Zhiyi Huang. Recognizing coverage functions. SICOMP, 29 0 (3): 0 1585--1599, 2015

    2015

  11. [11]

    Light RUM s

    Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Light RUM s. In ICML, pages 1888--1897, 2021

    2021

  12. [12]

    Muthukrishnan

    Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan. Comparing data streams using hamming norms (how to zero in). In VLDB, 2002

    2002

  13. [13]

    Concentration of Measure for the Analysis of Randomized Algorithms

    Devdatt P Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009

    2009

  14. [14]

    Learning coverage functions and private release of marginals

    Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of marginals. In COLT, pages 679--702, 2014

    2014

  15. [15]

    A B ayesian analysis of some nonparametric problems

    Thomas S Ferguson. A B ayesian analysis of some nonparametric problems. Ann. Stat., pages 209--230, 1973

    1973

  16. [16]

    Global min-cuts in RNC , and other ramifications of a simple min-cut algorithm

    David R Karger. Global min-cuts in RNC , and other ramifications of a simple min-cut algorithm. In SODA, pages 21--30, 1993

    1993

  17. [17]

    Constructing linear-sized spectral sparsification in almost-linear time

    Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. SICOMP, 47 0 (6): 0 2315--2336, 2018

    2018

  18. [18]

    Space lower bounds for itemset frequency sketches

    Edo Liberty, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman. Space lower bounds for itemset frequency sketches. In PODS, 2016

    2016

  19. [19]

    On the sub- G aussianity of the beta and D irichlet distributions

    Olivier Marchal and Julyan Arbel. On the sub- G aussianity of the beta and D irichlet distributions. Electronic Communications in Probability, 22 0 (54): 0 1--14, 2017

    2017

  20. [20]

    Serfling

    Robert J. Serfling. Probability inequalities for the sum in sampling without replacement. Ann. Stat., 2 0 (1): 0 39 -- 48, 1974

    1974

  21. [21]

    Graph sparsification by effective resistances

    Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In STOC, pages 563--568, 2008

    2008

  22. [22]

    Spectral sparsification of graphs

    Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SICOMP, 40 0 (4): 0 981--1025, 2011

    2011

  23. [23]

    Discrete Choice Methods with Simulation

    Kenneth E Train. Discrete Choice Methods with Simulation. Cambridge University Press, 2009

    2009

  24. [24]

    Learning interpretable decision rule sets: A submodular optimization approach

    Fan Yang, Kai He, Linxiao Yang, Hongxia Du, Jingbang Yang, Bo Yang, and Liang Sun. Learning interpretable decision rule sets: A submodular optimization approach. In NeurIPS, pages 27890--27902, 2021

    2021

  25. [25]

    Approximate F_2 -Sketching of Valuation Functions

    Grigory Yaroslavtsev and Samson Zhou. Approximate F_2 -Sketching of Valuation Functions . In APPROX/RANDOM, 2019

    2019