David P. Woodruff
# David P. Woodruff

David P. Woodruff, né en 1980, est professeur associé à l'École de science informatique de l'université Carnegie-Mellon. Il travaille sur la complexité de communications, les algorithmes de flux de données et leurs bornes inférieures, les algorithmes de graphes, l'apprentissage automatique, l'algèbre linéaire numérique, méthodes d'esquisses (sketching).

Il a obtenu un Ph. D. en informatique au Massachusetts Institute of Technology en 2007 sous la direction de Piotr Indyk avec une thèse intitulée Efficient and Private Distance Approximation in the Communication and Streaming $Models^,$ et a rejoint alors le IBM Almaden Research Center. Au deuxième sémestre 2018, il est aussi chercheur invité au Simons Institute for the Theory of Computing (en).

Il a obtenu le prix Presburger en 2014 alors qu'il travaillait encore au IBM Almaden Research Center de San Jose.

## Travaux

Woodruff a apporté d'importantes contributions à la théorie des flux de données, en créant de nouveaux algorithmes et en démontrant que certains algorithmes ne peuvent exister. Son travail a un impact sur d'autres domaines, y compris l'acquisition comprimée, l'apprentissage automatique et l'algèbre linéaire numérique.

Dans le domaine des flux de données, il a résolu le problème dit des éléments distincts « Distinct Elements Problem » en optimisant simultanément la quantité de mémoire utilisée, le temps nécessaire pour traiter chaque nouvelle entité et le temps nécessaire pour présenter une estimation du nombre d'éléments distincts dans le $flux^,.$

Dans le domaine de l'apprentissage automatique, il a utilisé ses résultats antérieurs sur les flux de données pour concevoir des algorithmes sous-linéaires pour le problème de classification linéaire et le problème du cercle $minimum^,.$

En algèbre linéaire numérique, il a développé les premiers algorithmes d'approximation et de régression de rang inférieur qui fonctionnent dans le temps proportionnellement au nombre d'entrées non nulles de la matrice d'entrée. Ses travaux ont également donné lieu à des brevets portant sur les flux de données et leurs applications.

Il a publié un long article de présentation de la problématique des esquisses (sketching).

