Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings

Summary: Establishes sharp sparsity–dimension lower bounds for oblivious subspace embeddings, recovering explicit d²/ε² dependence at low sparsity. A second regime yields strong d- and ε-dependent bounds, substantially improving prior results and exposing a broader m–d–ε–s–δ trade-off. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 2042
Venue: PODS
Year: 2026
Pagerank: -
Overall Rank: 13,287 | 8.84%
DOI: 10.1145/3801912

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 (Nanjing University)

BibTeX Citation

@inproceedings{li_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings}},
        url = {https://dl.acm.org/doi/10.1145/3801912},
        doi = {10.1145/3801912},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Li, Yi and Liu, Mingmou},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
11,529	Lower Bounds for Sparse Oblivious Subspace Embeddings	2022	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,194	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS
2	5,668	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS
3	5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
4	11,368	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS
5	13,406	High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data	2022	PODS
6	10,181	Representation Obliviousness and Pseudodeterminism in Streaming Algorithms	2026	PODS
7	10,162	On Sketching Trimmed Statistics	2026	PODS
8	10,168	Tight Lower Bounds for l2 Sampling	2026	PODS
9	7,918	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS
10	11,529	Lower Bounds for Sparse Oblivious Subspace Embeddings	2022	PODS