David P. Woodruff

David P. Woodruff, né en 1980, est professeur associé à l'École de science informatique de l'université Carnegie-Mellon[1]. 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)[2].

Pour les articles homonymes, voir Woodruff.

David P. Woodruff
Naissance
Nationalité Américain
Domaines informatique théorique, acquisition comprimée, algorithmes de flux de données
Institutions université Carnegie-Mellon, IBM Almaden Research Center
Diplôme Ph. D.
Formation Massachusetts Institute of Technology
Directeur de thèse Piotr Indyk
Renommé pour problématique des esquisses (sketching)
Distinctions prix Presburger (2014)
Site www.cs.cmu.edu/~dwoodruf/

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[3],[4] 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)[5].

Il a obtenu le prix Presburger en 2014[6] 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[6].

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[6],[7].

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[8],[9].

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[10]. Ses travaux ont également donné lieu à des brevets portant sur les flux de données et leurs applications[6].

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

Notes et références
  1. David Woodruff sur l'annuaire de l'université Carnégie-Mellon.
  2. Page personnelle de David P. Woodruff
  3. (en) « David P. Woodruff », sur le site du Mathematics Genealogy Project
  4. La thèse de Woodruff est accessible sur sa page personnelle.
  5. Divid Woodruff visiting scientist.
  6. Presburger Award 2014
  7. Daniel M. Kane, Jelani Nelson et David P. Woodruff, « An optimal algorithm for the distinct elements problem », PODS '10 Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems,‎ , p. 41-52 (DOI 10.1145/1807085.1807094).
  8. Kenneth L. Clarkson, Elad Hazan et David P. Woodruff, « Sublinear optimization for machine learning », Journal of the ACM, vol. 59, no 5,‎ , p. 1–49 (ISSN 0004-5411, DOI 10.1145/2371656.2371658).
  9. La version finale de l'article présenté en 2010 au FOCS a obtenu le Pat Goldberg Best Paper Award d'IBM.
  10. Kenneth L. Clarkson et David P. Woodruff, « Low rank approximation and regression in input sparsity time », STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing,‎ , p. 81-90 (DOI 10.1145/2488608.2488620).
  11. « Sketching as a Tool for Numerical Linear Algebra », Foundations and Trends in Theoretical Computer Science, vol. 10, nos 1-2,‎ , p. 1-157 (lire en ligne)

Liens externes
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.