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: 1893
Venue: PODS
Year: 2022
Pagerank: 5.0723324e-05
Overall Rank: 11,587 | 20.78%
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,340	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
106	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.0003356052
538	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016877923
7,546	Private Incremental Regression	2017	PODS	5.5795657e-05

Semantically Similar Papers

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