David P. Woodruff

Numerical Linear Algebra in the Sliding Window Model

2018 · arXiv (Cornell University)

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in the data stream form the underlying set. Although most existing work in the sliding …

Computing Approximate $\ell_p$ Sensitivities

2023 · arXiv (Cornell University)

Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation …

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

2025 · arXiv (Cornell University)

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 first consider average-case guarantees. A folklore upper bound …