Lower Bounds for Sparse Oblivious Subspace Embeddings

Summary: Proves tight lower bounds for sparse oblivious subspace embeddings: any OSE with one nonzero per column requires m = Ω(d^2/(ε^2 δ)), implying Count-Sketch is optimal. For 1/(9ε) nonzeros/column they show m = Ω(ε^{O(δ)} d^2), improving prior Ω(ε^2 d^2). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3c2b5938335a3636
Venue: PODS
Year: 2022
Pagerank: 4.9793485e-05
Overall Rank: 11,838 | 20.41%
DOI: 10.1145/3517804.3526224

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yi Li (Nanyang Technological University)
2. Mingmou Liu (Nanyang Technological University)

BibTeX Citation

@inproceedings{li_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Lower Bounds for Sparse Oblivious Subspace Embeddings}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3526224},
        doi = {10.1145/3517804.3526224},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Li, Yi and Liu, Mingmou},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,577	Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings	2026	PODS	-

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
105	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033638251
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016929744
7,663	Private Incremental Regression	2017	PODS	5.4772833e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,720	High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data	2022	PODS
2	4,283	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS
3	10,379	On Sketching Trimmed Statistics	2026	PODS
4	8,094	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS
5	9,559	Optimal Matrix Sketching over Sliding Windows	2024	VLDB
6	8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS
7	5,910	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD
8	10,385	Tight Lower Bounds for l2 Sampling	2026	PODS
9	8,085	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS
10	13,577	Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings	2026	PODS