David P. Woodruff
Affiliations: Carnegie Mellon University, PA, USA
 IBM Almaden Research Center (former)
According to our database^{1},
David P. Woodruff
authored at least 286 papers
between 2002 and 2022.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Online presence:

on orcid.org

on cs.cmu.edu
On csauthors.net:
Bibliography
2022
ACM Trans. Algorithms, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
CoRR, 2022
Proceedings of the 2022 ACMSIAM Symposium on Discrete Algorithms, 2022
Proceedings of the 2022 ACMSIAM Symposium on Discrete Algorithms, 2022
NearOptimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.
Proceedings of the 2022 ACMSIAM Symposium on Discrete Algorithms, 2022
A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World.
Proceedings of the Research in Computational Molecular Biology, 2022
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
2021
IEEE Trans. Inf. Theory, 2021
ACM Trans. Algorithms, 2021
SIGMOD Rec., 2021
SIAM J. Comput., 2021
SIAM J. Comput., 2021
CoRR, 2021
CoRR, 2021
CoRR, 2021
CoRR, 2021
CoRR, 2021
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020.
CoRR, 2021
Exponentially Improved Dimensionality Reduction for 𝓁<sub>1</sub>: Subspace Embeddings and Independence Testing.
CoRR, 2021
CoRR, 2021
Proceedings of the ThirtySeventh Conference on Uncertainty in Artificial Intelligence, 2021
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021
Optimal <i>ℓ</i><sub>1</sub> Column Subset Selection and a Fast PTAS for Low Rank Approximation.
Proceedings of the 2021 ACMSIAM Symposium on Discrete Algorithms, 2021
Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2021
Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 38th International Conference on Machine Learning, 2021
Proceedings of the 9th International Conference on Learning Representations, 2021
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
Proceedings of the Conference on Learning Theory, 2021
Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing.
Proceedings of the Conference on Learning Theory, 2021
Proceedings of the Conference on Learning Theory, 2021
Proceedings of the 36th Computational Complexity Conference, 2021
Proceedings of the Approximation, 2021
2020
ACM Trans. Algorithms, 2020
Electron. Colloquium Comput. Complex., 2020
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes.
CoRR, 2020
CoRR, 2020
Optimal 𝓁<sub>1</sub> Column Subset Selection and a Fast PTAS for Low Rank Approximation.
CoRR, 2020
CoRR, 2020
CoRR, 2020
CoRR, 2020
CoRR, 2020
LSFJoin: Locality Sensitive Filtering for Distributed AllPairs Set Similarity Under Skew.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 2024, 2020, 2020
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, 2020
Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, 2020
Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
Proceedings of the 37th International Conference on Machine Learning, 2020
Proceedings of the 37th International Conference on Machine Learning, 2020
Proceedings of the 8th International Conference on Learning Representations, 2020
Proceedings of the 8th International Conference on Learning Representations, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
VectorMatrixVector Queries for Solving Linear Algebra, Statistics, and Graph Problems.
Proceedings of the Approximation, 2020
Proceedings of the Approximation, 2020
Proceedings of the Approximation, 2020
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020
2019
An Optimal Algorithm for ℓ<sub>1</sub>Heavy Hitters in Insertion Streams and Related Problems.
ACM Trans. Algorithms, 2019
SIAM J. Comput., 2019
J. Mach. Learn. Res., 2019
Electron. Colloquium Comput. Complex., 2019
CoRR, 2019
CoRR, 2019
CoRR, 2019
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Research in Computational Molecular Biology, 2019
Proceedings of the 38th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the 36th International Conference on Machine Learning, 2019
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$means Clustering.
Proceedings of the 36th International Conference on Machine Learning, 2019
Proceedings of the 36th International Conference on Machine Learning, 2019
Separating kPlayer from tPlayer OneWay Communication, with Applications to Data Streams.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Proceedings of the 49. Jahrestagung der Gesellschaft für Informatik, 50 Jahre Gesellschaft für Informatik, 2019
Proceedings of the 35th International Symposium on Computational Geometry, 2019
Proceedings of the Conference on Learning Theory, 2019
Proceedings of the Conference on Learning Theory, 2019
Proceedings of the Conference on Learning Theory, 2019
Proceedings of the Approximation, 2019
Proceedings of the Approximation, 2019
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019
Proceedings of the ThirtyThird AAAI Conference on Artificial Intelligence, 2019
2018
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018
Electron. Colloquium Comput. Complex., 2018
CoRR, 2018
CoRR, 2018
Leveraging WellConditioned Bases: Streaming \& Distributed Summaries in Minkowski pNorms.
CoRR, 2018
CoRR, 2018
CoRR, 2018
Proceedings of the 37th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2018
Proceedings of the 37th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2018
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018
Leveraging WellConditioned Bases: Streaming and Distributed Summaries in Minkowski pNorms.
Proceedings of the 35th International Conference on Machine Learning, 2018
Proceedings of the 35th International Conference on Machine Learning, 2018
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
Proceedings of the Approximation, 2018
Proceedings of the Approximation, 2018
Proceedings of the Approximation, 2018
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018
2017
SIAM J. Matrix Anal. Appl., 2017
SIAM J. Comput., 2017
NII Shonan Meet. Rep., 2017
Distributed Comput., 2017
Dagstuhl Reports, 2017
CoRR, 2017
CoRR, 2017
Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s<sub>2</sub>Regularization.
CoRR, 2017
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
Proceedings of the 36th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2017
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
Proceedings of the 34th International Conference on Machine Learning, 2017
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
Proceedings of the 25th Annual European Symposium on Algorithms, 2017
Proceedings of the Approximation, 2017
2016
IEEE Trans. Knowl. Data Eng., 2016
ACM Trans. Algorithms, 2016
SIAM J. Comput., 2016
SIAM J. Comput., 2016
Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 201610).
NII Shonan Meet. Rep., 2016
CoRR, 2016
CoRR, 2016
Algorithmica, 2016
Algorithmica, 2016
Algorithmica, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Communication lower bounds for statistical estimation problems via a distributed data processing inequality.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond.
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016
Nearlyoptimal bounds for sparse recovery in generic norms, with applications to <i>k</i>median sketching.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors.
Proceedings of the 35th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2016
An Optimal Algorithm for l1Heavy Hitters in Insertion Streams and Related Problems.
Proceedings of the 35th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems, 2016
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016
Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016
Proceedings of the 33nd International Conference on Machine Learning, 2016
Proceedings of the 19th International Conference on Database Theory, 2016
Proceedings of the 32nd IEEE International Conference on Data Engineering, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Proceedings of the 24th Annual European Symposium on Algorithms, 2016
Proceedings of the 31st Conference on Computational Complexity, 2016
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings.
Proceedings of the Approximation, 2016
2015
Electron. Colloquium Comput. Complex., 2015
Electron. Colloquium Comput. Complex., 2015
CoRR, 2015
Communicationoptimal Distributed Principal Component Analysis in the Columnpartition Model.
CoRR, 2015
CoRR, 2015
Nearlyoptimal bounds for sparse recovery in generic norms, with applications to $k$median sketching.
CoRR, 2015
Algorithmica, 2015
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
The Communication Complexity of Distributed SetJoins with Applications to Matrix Multiplication.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
Proceedings of the Approximation, 2015
2014
Found. Trends Theor. Comput. Sci., 2014
Bull. EATCS, 2014
CoRR, 2014
CoRR, 2014
Comb., 2014
On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model.
Proceedings of the Distributed Computing  28th International Symposium, 2014
Proceedings of the Symposium on Theory of Computing, 2014
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Proceedings of the 33rd ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2014
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014
Beyond set disjointness: the communication complexity of finding the intersection.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014
Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014
Proceedings of The 27th Conference on Learning Theory, 2014
2013
Optimal Bounds for JohnsonLindenstrauss Transforms and Streaming Problems with Subconstant Error.
ACM Trans. Algorithms, 2013
Proc. VLDB Endow., 2013
Subspace Embeddings and ℓ<sub>p</sub>Regression Using Exponential Random Variables
CoRR, 2013
CoRR, 2013
Proceedings of the Symposium on Theory of Computing Conference, 2013
Proceedings of the Symposium on Theory of Computing Conference, 2013
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 58, 2013
Proceedings of the COLT 2013, 2013
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013
2012
Lower Bounds for Local Monotonicity Reconstruction from TransitiveClosure Spanners.
SIAM J. Discret. Math., 2012
SIAM J. Comput., 2012
J. Mach. Learn. Res., 2012
A Quadratic Lower Bound for ThreeQuery Linear Locally Decodable Codes over Any Field.
J. Comput. Sci. Technol., 2012
J. ACM, 2012
The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1
CoRR, 2012
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Proceedings of the IEEE Statistical Signal Processing Workshop, 2012
Proceedings of the 31st ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2012
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
2011
Proceedings of the Distributed Computing  25th International Symposium, 2011
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Optimal Bounds for JohnsonLindenstrauss Transforms and Streaming Problems with SubConstant Error.
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Innovations in Computer Science, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the Algorithms  ESA 2011, 2011
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
2010
J. ACM, 2010
CoRR, 2010
Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, 2010
Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, 2010
Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, 2010
Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, 2010
Proceedings of the TwentyNinth ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2010
Proceedings of the TwentyNinth ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2010
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
2009
Proceedings of the Encyclopedia of Database Systems, 2009
Electron. Colloquium Comput. Complex., 2009
CoRR, 2009
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
Proceedings of the Database Theory, 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
CoRR, 2008
Proceedings of the Approximation, 2008
2007
Efficient and private distance approximation in the communication and streaming models.
PhD thesis, 2007
Electron. Colloquium Comput. Complex., 2007
The communication and streaming complexity of computing the longest common and increasing subsequences.
Proceedings of the Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2007
2006
IACR Cryptol. ePrint Arch., 2006
IACR Cryptol. ePrint Arch., 2006
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
Proceedings of the Approximation, 2006
2005
Electron. Colloquium Comput. Complex., 2005
Electron. Colloquium Comput. Complex., 2005
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
2004
IACR Cryptol. ePrint Arch., 2004
IACR Cryptol. ePrint Arch., 2004
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
Proceedings of the Twentythird ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, 2004
Proceedings of the Advances in Cryptology, 2004
2003
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
2002
Proceedings of the Advances in Cryptology  EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28, 2002