Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

Sandeep Silwal, David P. Woodruff, Qiuyi Zhang

We study beyond worst-case dimensionality reduction for $s$-sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We…