3 papers
cs.DS2022
Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
Yi Li, Mingmou Liu
An oblivious subspace embedding (OSE), characterized by parameters , is a random matrix such that for any -dimensional subspace $T\subse…
cs.DS2021
Lower Bounds for Sparse Oblivious Subspace Embeddings
Yi Li, Mingmou Liu
An oblivious subspace embedding (OSE), characterized by parameters , is a random matrix such that for any -dimensional subspace $T\subse…
cs.DS2021
On the Optimal Time/Space Tradeoff for Hash Tables
Michael A. Bender, Martín Farach-Colton, John Kuszmaul +2
For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art h…