David P. Woodruff

My current interests are communication complexity, data stream algorithms and lower bounds, graph algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery.


Contact: dwoodruf (at) cs (dot) cmu (dot) edu   

Copyright: Persons copying the material below should adhere to the terms of each author's copyright.


Book

2017 Course on Sketching as a Tool for Numerical Linear Algebra (more extensive slides than the 2016 ones below)

All slides for 12 1-hour lectures slides

Additional 2 1-hour lectures l1LowRankSlides  weightedLowRankSlides

 

Summer School 2016 Course Slides (Sketching as a Tool for Numerical Linear Algebra)

Below are slides for all lectures on days 1-3 and 3/4 of day 4

ppt version of the slides allLectures.pptx

pdf version of the slides allLectures.pdf

The other slides for day 4 are regressionM and lowRankM and weighted


 

Lecture Notes (MADALGO and BASICS)

Here are three lectures, slight variants of which were given at the MADALGO summer school on streaming 2015 as well as the BASICS summer school on communication complexity 2015. The first lecture is an introduction to information theory for data streams, the second contains direct sum theorems for data streams, and the third covers multiplayer communication complexity.

Lecture 1

Lecture 2

Lecture 3

 


Publications

 

2017


 

2016

 


2015


2014


2013


2012


2011


2010


2009


2008


2007


2006


2005


2004


2003


2002


DBLP

DBLP


Miscellaneous Papers