David P. Woodruff
3 papers in the PaperMetrix corpus
Papers by this author
-
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 …