DW
David P. Woodruff
cs.DScs.LGstat.MLcs.CCcs.NAmath.NAcs.DCcs.ITmath.ITcs.AI
On Valency
published · living versionsW_wmvytrdq·v1 · currentpublished
Beyond the Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
with Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu +2
1 version
W_yze4fmvm·v1published
W_zvejcjnj·v1published
Preprints & journals
274 papers in the corpus · 2008–2026On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions2610.27502v1 · Honghao Lin, Songbin Liu, Arian Maleki et al.2026 · 0 citationsarXiv
Symmetric Submodular Minimization from Comparisons2610.10518v1 · James Fox, David P. Woodruff2026 · 0 citationsarXiv
Optimal and Efficient Online Inverse Optimization2610.08735v1 · Anupam Gupta, Guru Guruganesh, Honghao Lin et al.2026 · 0 citationsarXiv
A Proof of the Most Informative Boolean Function Conjecture2609.24931v2 · Zijie Chen, Amin Gohari, Adel Javanmard et al.2026 · 0 citationsarXiv
High Probability Streaming Lower Bounds for Estimation2609.17286v1 · William Swartworth, David P. Woodruff, Samson Zhou2026 · 0 citationsarXiv
Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science2609.15983v2 · Honghao Lin, David P. Woodruff, Yuan Deng et al.2026 · 0 citationsarXiv
Nearly Optimal Strong Coresets for Subspace Approximation2608.26047v2 · Honghao Lin, Vahab Mirrokni, David P. Woodruff2026 · 0 citationsarXiv
TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability2608.09538v3 · Vincent Cohen-Addad, Dimitris Paparas, Ernest van Wijland et al.2026 · 0 citationsarXiv
A Near-Optimal Lower Bound for Prefix-Matrix Factorizations2608.08238v1 · Honghao Lin, Vahab Mirrokni, David P. Woodruff2026 · 0 citationsarXiv
SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant2608.05127v3 · Adel Javanmard, David P. Woodruff, Vahab Mirrokni2026 · 0 citationsarXiv
Pairwise-Independent Dithering for Single-Stage Hadamard Quantization2608.02564v2 · Honghao Lin, Vahab Mirrokni, David P. Woodruff2026 · 0 citationsarXiv
The Condition-Number Barrier in Sparse Least Squares2608.02588v1 · Honghao Lin, Vahab Mirrokni, David P. Woodruff2026 · 0 citationsarXiv
Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity2607.20393v2 · Rajesh Jayaram, Honghao Lin, Vahab Mirrokni et al.2026 · 0 citationsarXiv
The Adversarial Robustness of Sketching and Streaming Algorithms2607.14432v1 · David P. Woodruff, Samson Zhou2026 · 0 citationsarXiv
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams2607.06312v1 · Elena Gribelyuk, Honghao Lin, David P. Woodruff et al.2026 · 0 citationsarXiv
Towards Automating Scientific Review with Google's Paper Assistant Tool2606.28277v1 · Rajesh Jayaram, Drew Tyler, David Woodruff et al.2026 · 0 citationsarXiv
Active Learning with Low-Rank Structure for Data Selection2606.16045v1 · Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni et al.2026 · 0 citationsarXiv
Streaming Complexity Separations for Dense and Sparse Graphs2605.09814v1 · Yang P. Liu, Hoai-An Nguyen, Noah G. Singer et al.2026 · 0 citationsarXiv
SVD Provably Denoises Nearest Neighbor Data2604.03831v1 · Ravindran Kannan, Kijun Shin, David Woodruff2026 · 0 citationsarXiv
Better Bounds for the Distributed Experts Problem2603.09168v1 · David P. Woodruff, Samson Zhou2026 · 0 citationsarXiv
Distributed Algorithms for Euclidean Clustering2603.08615v1 · Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff et al.2026 · 0 citationsarXiv
Solving an Open Problem in Theoretical Physics using AI-Assisted Discovery2603.04735v1 · Michael P. Brenner, Vincent Cohen-Addad, David Woodruff2026 · 0 citationsarXiv
Learning-Augmented Moment Estimation on Time-Decay Models2603.02488v1 · Soham Nagawanshi, Shalini Panthangi, Chen Wang et al.2026 · 0 citationsarXiv
Consistent Low-Rank Approximation2603.02148v1 · David P. Woodruff, Samson Zhou2026 · 0 citationsarXiv
Adversarial Robustness on Insertion-Deletion Streams2602.20854v2 · Elena Gribelyuk, Honghao Lin, David P. Woodruff et al.2026 · 0 citationsarXiv
Aletheia tackles FirstProof autonomously2602.21201v3 · Tony Feng, Junehyuk Jung, Sang-hyun Kim et al.2026 · 0 citationsarXiv
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques2602.03837v3 · David P. Woodruff, Vincent Cohen-Addad, Lalit Jain et al.2026 · 4 citationsarXiv
Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information2601.09679v1 · Adel Javanmard, David P. Woodruff2026 · 1 citationarXiv
Online Learning with Limited Information in the Sliding Window Model2601.03533v1 · Vladimir Braverman, Sumegha Garg, Chen Wang et al.2026 · 0 citationsarXiv
JEPA-Reasoner: Decoupling Latent Reasoning from Token Generation2512.19171v3 · Bingyang Kelvin Liu, Ziyu Patrick Chen, David P. Woodruff2025 · 0 citationsarXiv
Perfect Sampling with Polylogarithmic Update Time2512.00632v1 · William Swartworth, David P. Woodruff, Samson Zhou2025 · 0 citationsarXiv
Combinatorial Optimization using Comparison Oracles2511.15142v2 · Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta et al.2025 · 0 citationsarXiv
Sampling in Distributed Data Streams with Applications to Adversarial Robustness2510.22816v1 · Honghao Lin, Zhao Song, David P. Woodruff et al.2025 · 0 citationsarXiv
Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams2510.18180v1 · Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie et al.2025 · 0 citationsarXiv
Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph2509.16180v2 · Gautam Kamath, Alireza F. Pour, Matthew Regehr et al.2025 · 0 citationsarXiv
Unbiased Insights: Optimal Streaming Algorithms for Sampling, the Forget Model, and Beyond2508.07067v3 · Honghao Lin, Hoai-An Nguyen, William Swartworth et al.2025 · 0 citationsarXiv
Multipass Linear Sketches for Geometric LP-Type Problems2507.11484v2 · N. Efe Cekirge, William Gay, David P. Woodruff2025 · 0 citationsarXiv
On Fine-Grained Distinct Element Estimation2506.22608v1 · Ilias Diakonikolas, Daniel M. Kane, Jasper C.H. Lee et al.2025 · 0 citationsarXiv
On Sketching Trimmed Statistics2506.07342v2 · Honghao Lin, Hoai-An Nguyen, David P. Woodruff2025 · 0 citationsarXiv
On Differential Privacy for Adaptively Solving Search Problems via Sketching2506.05503v1 · Shiyuan Feng, Ying Feng, George Z. Li et al.2025 · 0 citationsarXiv
Efficient Attention via Pre-Scoring: Prioritizing Informative Keys in Transformers2505.11040v4 · Zhexiang Li, Haoyu Wang, Yutong Bao et al.2025 · 0 citationsarXiv
Guessing Efficiently for Constrained Subspace Approximation2504.20883v1 · Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu et al.2025 · 0 citationsarXiv
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model2504.21175v1 · Shiyuan Feng, William Swartworth, David P. Woodruff2025 · 0 citationsarXiv
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures2504.18394v2 · Alina Ene, Alessandro Epasto, Vahab Mirrokni et al.2025 · 0 citationsarXiv
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings2504.16229v1 · Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff et al.2025 · 0 citationsarXiv
Range Counting Oracles for Geometric Problems2504.15292v1 · Anne Driemel, Morteza Monemizadeh, Eunjin Oh et al.2025 · 0 citationsarXiv
Perfect Sampling in Turnstile Streams Beyond Small Moments2504.07237v1 · David P. Woodruff, Shenghao Xie, Samson Zhou2025 · 0 citationsarXiv
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness2503.19629v1 · Elena Gribelyuk, Honghao Lin, David P. Woodruff et al.2025 · 2 citationsarXiv
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors2502.19865v1 · Sandeep Silwal, David P. Woodruff, Qiuyi Zhang2025 · 0 citationsarXiv
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra2502.08029v2 · Raphael A. Meyer, William Swartworth, David P. Woodruff2025 · 0 citationsarXiv
Career total: 529 works. 274 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.