Mingmou Liu

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2022

Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings

Yi Li, Mingmou Liu

An oblivious subspace embedding (OSE), characterized by parameters $m, n, d, ε, δ$ , is a random matrix $Π \in R^{m \times n}$ such that for any $d$ -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 $m, n, d, ε, δ$ , is a random matrix $Π \in R^{m \times n}$ such that for any $d$ -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…