David P. Woodruff, né en 1980, est professeur associé à l'École de science informatique de l'université Carnegie-MellonDavid Woodruff sur l'annuaire de l'université Carnégie-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)Page personnelle de David P. Woodruff.
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 ModelsLa thèse de Woodruff est accessible sur sa page personnelle. et a rejoint alors le IBM Almaden Research Center. Au deuxième sémestre 2018, il est aussi chercheur invité au Divid Woodruff visiting scientist..
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 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.La version finale de l'article présenté en 2010 au FOCS a obtenu le Pat Goldberg Best Paper Award d'IBM..
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).
Notes et références
Liens externes Page personnelle de David P. Woodruff Publications de David Woolruff sur DBLP
Catégorie:Naissance en 1980 Catégorie:Mathématicien américain du XXIe siècle Catégorie:Informaticien américain du XXIe siècle Catégorie:Professeur à l'université Carnegie-Mellon Catégorie:Universitaire américain du XXIe siècle