David P. Woodruff
where else to find them
linkedin:david-woodruff-5041885
what they talk about
all 7 in the filters
where they keep going back
- ITCS2 editions2022–2023
- Real-Time Decision Making2 editions2016–2018
all 12 in the filters
on a stage with
all 12 in the filters
who talks about the same things
- Michael Kapralov7 talks
- Samson Zhou4 talks
- Toniann Pitassi5 talks
- Dor Minzer8 talks
- Mark Braverman5 talks
- Amin Saberi6 talks
| title | conference | date |
|---|---|---|
| Long-context Attention in Near-Linear Time | Extroverted Sublinear Algorithms 2024 | 2024-06-17 |
HyperAttention claims near-linear time attention by sampling columns and rows based on two fine-grained parameters: the max column norm of the row-normalized… | ||
| Sketching and Randomized Linear Algebra | Sublinear Algorithms Boot Camp 2024 | 2024-05-21 |
Shows that random sketches preserve norms and dot products via the Johnson-Lindenstrauss lemma (r = Θ(1/ε^2 log 1/δ)), extend to approximate matrix product… | ||
| Tight Bounds for Active lp Regression and Beyond | Optimization and Algorithm Design 2023 | 2023-11-27 |
Gives tight query bounds for active lp regression with concrete algorithms: sensitivity sampling followed by Lewis-weight chaining and a label-partition that… | ||
| Testing Positive Semidefiniteness and Eigenvalue Approximation | Sketching and Algorithm Design 2023 | 2023-10-09 |
Presents concrete testers and tight bounds: for Schatten-1 norm, adaptive matrix‑vector Krylov methods use a polynomial filtering trick to get 1/epsilon^{1/3}… | ||
| Streaming Euclidean k-median and k-means with o(log n) Space | Sketching and Algorithm Design 2023 | 2023-10-09 |
Presents a streaming algorithm that breaks the long standing Omega(log(n Delta)) word barrier for insertion-only Euclidean (k,z)-clustering by producing a… | ||
| Recovery from Non-Decomposable Distance Oracles | ITCS 2023 | 2023-01-10 |
Study of locating an unknown length-n sequence from distance queries for non-decomposable metrics focuses on DTW and gives concrete bounds and constructions… | ||
| An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes | ITCS 2022 | 2022-01-31 |
Claims a one plus epsilon PTAS for tournament Feedback Arc Set running in semi‑streaming memory using sampling and local moves. Algorithm approximates… | ||
| Noisy Boolean Hidden Matching with Applications | ITCS 2022 | 2022-01-31 |
Defines p-noisy Boolean hidden matching where each matching edge flips independently with probability p and proves the plaintext protocol is optimal, giving… | ||
| Intro and Foundations of Data Science I | Foundations of Data Science Boot Camp 2018 | 2018-08-27 |
A compact course first promotes a finite-moment method that replaces exponential moment proofs with Rth moments and an R! bound to get Gaussian-like moment… | ||
| Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I | Foundations of Data Science Boot Camp 2018 | 2018-08-27 |
Shows that CountSketch matrices (hash rows, random ±1 signs) give a subspace embedding for regression with one non-zero per column and k = Θ(d^2/ε^2) rows, so… | ||
| Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II | Foundations of Data Science Boot Camp 2018 | 2018-08-27 |
Shows that CountSketch JL moment (L=2) gives an unbiased subspace embedding with variance O(1/K) and needs about K = 2/(ε^2 δ) rows to get the desired moment… | ||
| Relative Error Tensor Low Rank Approximation | Real-Time Decision Making 2018 | 2018-04-30 |
Shows an algorithm that outputs a rank R = O(K^2/ε^2) tensor achieving Frobenius (1+ε) relative error to the best rank-K solution, runs in input-sparsity time… | ||
| New Algorithms for Heavy Hitters in Data Streams | Real-Time Decision Making | 2016-07-01 |
One-pass algorithm finds L2 heavy hitters in insertion-only streams using nearly log N bits of space (previous best was ~log^2 N), giving an optimal bound… | ||
| Input Sparsity and Hardness for Linear Algebra Problems | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Proves approximate Frobenius low-rank can run in input-sparsity time by sketching: multiply A by a sparse count sketch (one nonzero per column), project rows… | ||
| Counting Distinct Elements in the Message Passing Model | Information Theory in Complexity Theory and Combinatorics 2015 | 2015-04-24 |
Proves an Omega communication lower bound: the randomized distributional sum‑disjointness task in the k‑party point‑to‑point model requires omega(n k) bits by… | ||
| Sketching for M-Estimators: A Unified Approach to Robust Regression | Information Theory, Learning and Big Data (Simons Institute, 2015) | 2015-03-16 |
Presents algorithms that compress an N×D regression to about poly(D) log N rows using sparse sign sketches and diagonal subsampling, then solves the smaller… | ||
| Sketching as a Tool for Numerical Linear Algebra | Fast Algorithms via Spectral Methods 2014 | 2014-12-01 |
Shows concrete sketching recipes and runtime guarantees: Gaussian JL needs K = Θ(d/ε²) but is dense; a fast JL (Hadamard+sign+sampling) gives O(nd log n) time… | ||
| How Robust are Linear Sketches to Adaptive Inputs? | Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) | 2013-09-16 |
Shows a reconstruction attack that, given oracle access to any r‑row linear sketch, uses Gaussian query distribution and polynomially many adaptive queries to… | ||
| nothing matches | ||