vix.ing · top · new · best · stats · spec

David P. Woodruff

  1. HyperAttention: Long-context Attention in Near-Linear Time
    2023/10/09 by Insu Han, Rajesh Jayaram, Han, Insu +9 · 1 voice · 13 citations
    #cs.LG #cs.AI
  2. Fast approximation of matrix coherence and statistical leverage
    2011/09/18 by Petros Drineas, Malik Magdon‐Ismail, Drineas, Petros +5 · 15 citations
    Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications
  3. Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
    2026/02/03 by David P. Woodruff, Vincent Cohen-Addad, Lalit Jain +33 · 8 voices · 1 citation
    #cs.CL #cs.AI
  4. Hutch++: Optimal Stochastic Trace Estimation
    2020/10/19 by Raphael A. Meyer, Meyer, Raphael A., Cameron Musco +5 · 1 voice · 12 citations
    Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #cs.DS #cs.LG #math.NA
  5. Optimal approximate matrix product in terms of stable rank
    2015/07/08 by Michael B. Cohen, Cohen, Michael B., Jelani Nelson +3 · 11 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  6. Communication Lower Bounds for Statistical Estimation Problems via a\n Distributed Data Processing Inequality
    2015/06/23 by Mark Braverman, Ankit Garg, Braverman, Mark +7 · 6 citations
    Mathematics · Computer Science · #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data
  7. Frequent Directions : Simple and Deterministic Matrix Sketching
    2015/01/08 by Mina Ghashami, Edo Liberty, Ghashami, Mina +5 · 5 citations
    Computer Science · Engineering · #68W40 (Primary) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  8. Learning Augmented Binary Search Trees
    2022/06/24 by Honghao Lin, Lin, Honghao, Tian Luo +3 · 6 citations
    Computer Science · #Music and Audio Processing #Algorithms and Data Compression #Machine Learning and Data Classification
  9. Learning-Augmented k-means Clustering
    2021/10/27 by Jon C. Ergun, Zhili Feng, Ergun, Jon C. +7 · 5 citations
    Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
  10. Learning the Positions in CountSketch
    2020/07/20 by Simin Liu, Tianrui Liu, Liu, Simin +7 · 4 citations
    Computer Science · #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA)
  11. Optimal lower bounds for universal relation, and for samplers and\n finding duplicates in streams
    2017/04/03 by Michael Kapralov, Kapralov, Michael, Jelani Nelson +9 · 3 citations
    Computer Science · #Privacy-Preserving Technologies in Data #Cryptography and Data Security #Internet Traffic Analysis and Secure E-voting
  12. Pseudo-deterministic Streaming
    2019/11/26 by Shafi Goldwasser, Ofer Grossman, Goldwasser, Shafi +5 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
  13. Transitive-Closure Spanners
    2008/08/13 by Arnab Bhattacharyya, Elena Grigorescu, Bhattacharyya, Arnab +7 · 2 citations
    Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.2.3 #Geotechnical Engineering and Underground Structures
  14. Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
    2024/02/27 by Kyriakos Axiotis, Vincent Cohen-Addad, Axiotis, Kyriakos +13 · 5 citations
    Computer Science · #Anomaly Detection Techniques and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and Data Classification
  15. Learning the Positions in CountSketch
    2023/06/11 by Li, Yi, Simin Liu, Lin, Honghao +5 · 4 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  16. Sharper Bounds for Regularized Data Fitting
    2016/11/10 by Haim Avron, Kenneth L. Clarkson, Avron, Haim +3 · 2 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  17. Relative Error Tensor Low Rank Approximation
    2017/04/26 by Zhao Song, David P. Woodruff, Song, Zhao +3 · 2 citations
    Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Matrix Theory and Algorithms #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
  18. BPTree: an ℓ2 heavy hitters algorithm using constant memory
    2016/03/02 by Vladimir Braverman, Braverman, Vladimir, Stephen R. Chestnut +9 · 2 citations
    Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  19. Sketching for Kronecker Product Regression and P-splines
    2017/12/27 by Huaian Diao, Diao, Huaian, Zhao Song +5 · 2 citations
    Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications #Matrix Theory and Algorithms
  20. Learning a Latent Simplex in Input-Sparsity Time
    2021/05/17 by Ainesh Bakshi, Chiranjib Bhattacharyya, Bakshi, Ainesh +7 · 2 citations
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms
  21. Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients
    2024/06/25 by Aashiq Muhamed, Oscar Li, Muhamed, Aashiq +7 · 4 citations
    Computer Science · #Advanced Neural Network Applications #Machine Learning and Algorithms #Neural Networks and Applications
  22. Near Optimal Linear Algebra in the Online and Sliding Window Models
    2018/05/10 by Vladimir Braverman, Petros Drineas, Braverman, Vladimir +11 · 2 citations
    Engineering · Computer Science · Decision Sciences · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Advanced Bandit Algorithms Research
  23. Input Sparsity and Hardness for Robust Subspace Approximation
    2015/10/20 by Kenneth L. Clarkson, Clarkson, Kenneth L., David P. Woodruff +1 · 2 citations
    Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs
  24. The Fast Cauchy Transform and Faster Robust Linear Regression
    2012/07/19 by Kenneth L. Clarkson, Petros Drineas, Clarkson, Kenneth L. +9 · 1 citation
    Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Mathematical Approximation and Integration #Machine Learning and Algorithms
  25. Online Lewis Weight Sampling
    2022/07/17 by David P. Woodruff, Woodruff, David P., Taisuke Yasuda +1 · 2 citations
    Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  26. How to Fake Multiply by a Gaussian Matrix
    2016/06/18 by Michael Kapralov, Vamsi K. Potluru, Kapralov, Michael +3 · 1 citation
    Computer Science · Mathematics · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Tensor decomposition and applications
  27. Improving the Bit Complexity of Communication for Distributed Convex Optimization
    2024/03/28 by Mehrdad Ghadiri, Ghadiri, Mehrdad, Yin Tat Lee +9 · 2 citations
    Computer Science · #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)
  28. High-Dimensional Geometric Streaming in Polynomial Space
    2022/04/08 by David P. Woodruff, Taisuke Yasuda, Woodruff, David P. +1 · 1 citation
    Computer Science · Engineering · #Computational Geometry and Mesh Generation #Topological and Geometric Data Analysis #Advanced Numerical Analysis Techniques
  29. Optimal Sketching for Trace Estimation
    2021/11/01 by Shuli Jiang, Hai Pham, Jiang, Shuli +5 · 1 citation
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs
  30. Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products
    2022/02/10 by Ainesh Bakshi, Bakshi, Ainesh, Kenneth L. Clarkson +3 · 1 citation
    Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  31. Memory Bounds for the Experts Problem
    2022/04/21 by Vaidehi Srinivas, Srinivas, Vaidehi, David P. Woodruff +5 · 1 citation
    Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
  32. Weighted Reservoir Sampling from Distributed Streams
    2019/01/01 by Rajesh Jayaram, Gokarna Sharma, Jayaram, Rajesh +5 · 1 citation
    Computer Science · #Machine Learning and Algorithms #Data Stream Mining Techniques #Privacy-Preserving Technologies in Data
  33. Optimal Query Complexities for Dynamic Trace Estimation
    2022/09/30 by David P. Woodruff, Woodruff, David P., Fred Zhang +3 · 1 citation
    Computer Science · #Bayesian Modeling and Causal Inference #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques
  34. Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
    2019/09/29 by Huaian Diao, Rajesh Jayaram, Diao, Huaian +7 · 1 citation
    Computer Science · #Face and Expression Recognition #Machine Learning and Data Classification #Neural Networks and Applications
  35. Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression
    2023/03/31 by Alexander Munteanu, Simon Omlor, Munteanu, Alexander +3 · 1 citation
    Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Face and Expression Recognition
  36. ℓp-Regression in the Arbitrary Partition Model of Communication
    2023/07/11 by Yi Li, Honghao Lin, Li, Yi +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data
  37. A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches
    2024/09/24 by Elena Gribelyuk, Honghao Lin, Gribelyuk, Elena +7 · 2 citations
    Computer Science · Engineering · #Adversarial Robustness in Machine Learning #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques
  38. Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
    2024/12/08 by David P. Woodruff, Samson Zhou, Woodruff, David P. +1 · 2 citations
    Computer Science · #Adversarial Robustness in Machine Learning #Physical Unclonable Functions (PUFs) and Hardware Security #Cryptographic Implementations and Security
  39. Low Rank Approximation with Entrywise ℓ1-Norm Error
    2016/11/03 by Zhao Song, David P. Woodruff, Song, Zhao +3 · 1 citation
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  40. Fast White-Box Adversarial Streaming Without a Random Oracle
    2024/06/10 by Ying Feng, Feng, Ying, Aayush Jain +3 · 1 citation
    Computer Science · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Security in Wireless Sensor Networks #Video Surveillance and Tracking Methods
  41. Streaming Algorithms with Few State Changes
    2024/06/10 by Rajesh Jayaram, David P. Woodruff, Jayaram, Rajesh +3 · 1 citation
    Computer Science · #Caching and Content Delivery #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  42. On Differential Privacy and Adaptive Data Analysis with Bounded Space
    2023/02/11 by Itai Dinur, Dinur, Itai, Uri Stemmer +5 · 1 citation
    Computer Science · #Privacy-Preserving Technologies in Data #Cryptography and Data Security #Complexity and Algorithms in Graphs
  43. A New Information Complexity Measure for Multi-pass Streaming with Applications
    2024/03/29 by Mark Braverman, Sumegha Garg, Braverman, Mark +9 · 1 citation
    Computer Science · #Cloud Computing and Resource Management #Quantum Computing Algorithms and Architecture #IoT and Edge/Fog Computing
  44. The Adversarial Robustness of Sketching and Streaming Algorithms
    2026/07/15 by David P. Woodruff, Samson Zhou
    #cs.DS
  45. Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
    2026/07/22 by Rajesh Jayaram, Honghao Lin, Vahab Mirrokni +1
    #cs.DS #cs.IR