Publications by David Woodruff

Preprint

A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

2026
Lin H, Mirrokni V, Woodruff DP

Preprint

A Proof of the Most Informative Boolean Function Conjecture

2026
Chen Z, Gohari A, Javanmard A, Lin H, Mirrokni V, Nair C, Woodruff DP

Preprint

Accelerating Scientific Research with Gemini: Case Studies and Common Techniques

2026
Woodruff D, and others

Preprint

Active Learning with Low-Rank Structure for Data Selection

2026
Cohen-Addad V, Kunapuli S, Mirrokni V, Nikdan M, Woodruff DP, Zhou S

Preprint

Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

2026
Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S

Preprint

Adversarial Robustness on Insertion-Deletion Streams

2026
Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S

Conference

Adversarial Robustness on Insertion-Deletion Streams

2026 • Annual ACM Symposium on Theory of Computing • 2278-2289
Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S

Preprint

Aletheia tackles FirstProof autonomously

2026
Feng T, Jung J, Kim S-H, Pagano C, Gukov S, Tsai C-C, Woodruff D, Javanmard A, Mokhtari A, Hwang D, Chervonyi Y, Lee JN, Bingham G, Trinh TH, Mirrokni V, Le QV, Luong T

Preprint

Combinatorial Optimization using Comparison Oracles

2026
Cohen-Addad V, d'Orsi T, Gupta A, Guruganesh G, Lee E, Leme RP, Panigrahi D, Pittu MR, Schneider J, Woodruff DP

Conference

Combinatorial Optimization using Comparison Oracles

2026 • Annual ACM Symposium on Theory of Computing • 1995-2006
Cohen-Addad V, d'Orsi T, Gupta A, Guruganesh G, Lee E, Leme RP, Panigrahi D, Pittu MR, Schneider J, Woodruff DP

Preprint

Distributed Algorithms for Euclidean Clustering

2026
Cohen-Addad V, Wang L, Woodruff DP, Zhou S

Preprint

High Probability Streaming Lower Bounds for $F_2$ Estimation

2026
Swartworth W, Woodruff DP, Zhou S

Conference

High Probability Streaming Lower Bounds for F2 Estimation

2026 • Leibniz International Proceedings in Informatics • 392:
Swartworth W, Woodruff DP, Zhou S

Conference

Lp Sampling in Distributed Data Streams with Applications to Adversarial Robustness

2026 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 2026-January:4342-4409
Lin H, Song Z, Woodruff DP, Xie S, Zhou S

Preprint

Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

2026
Jayaram R, Lin H, Mirrokni V, Woodruff DP

Preprint

Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation

2026
Lin H, Mirrokni V, Woodruff DP

Journal Article

On Sketching Trimmed Statistics

2026 • Proceedings of the ACM on Management of Data • 4(2):
Lin H, Nguyen H-A, Woodruff DP

Preprint

On Sketching Trimmed Statistics

2026
Lin H, Nguyen H-A, Woodruff DP

Conference

Online Learning with Limited Information in the Sliding Window Model

2026 • PROCEEDINGS OF THE 2026 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA • 3249-3297
Braverman V, Garg S, Wang C, Woodruff DP, Zhou S

Preprint

Online Learning with Limited Information in the Sliding Window Model

2026
Braverman V, Garg S, Wang C, Woodruff DP, Zhou S

Preprint

Optimal and Efficient Online Inverse Optimization

2026
Gupta A, Guruganesh G, Lin H, Mirrokni V, Leme RP, Woodruff DP

Preprint

Pairwise-Independent Dithering for Single-Stage Hadamard Quantization

2026
Lin H, Mirrokni V, Woodruff DP

Conference

Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information

2026 • IEEE International Symposium on Information Theory - Proceedings • 00:1-6
Javanmard A, Woodruff DP

Preprint

Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information

2026
Javanmard A, Woodruff DP

Preprint

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph

2026
Kamath G, Pour AF, Regehr M, Woodruff DP

At a Glance

Academic Offerings

Admissions

Directory Submenu

People

Explore the Field

Publications by David Woodruff

Preprint

Preprint

Preprint

Preprint

Preprint

Preprint

Conference

Preprint

Preprint

Conference

Preprint

Preprint

Conference

Conference

Preprint

Preprint

Journal Article

Preprint

Conference

Preprint

Preprint

Preprint

Conference

Preprint

Preprint

At a Glance

Academic Offerings

Admissions

Directory Submenu

People

Explore the Field

What can we help you find?

Preprint

Preprint

Preprint

Preprint

Preprint

Preprint

Conference

Preprint

Preprint

Conference

Preprint

Preprint

Conference

Conference

Preprint

Preprint

Journal Article

Preprint

Conference

Preprint

Preprint

Preprint

Conference

Preprint

Preprint