David P. Woodruff

David P. Woodruff Nøkkeldata
Fødsel 1980
Nasjonalitet amerikansk
Områder teoretisk databehandling , komprimert oppkjøp , algoritmer for dataflyt
Institusjoner Carnegie-Mellon University , IBM Almaden Research Center
Diplom Ph. D.
Opplæring Massachusetts Institute of Technology
Veileder Piotr indyk
Kjent for problematiske skisser ( skisser )
Utmerkelser Presburger-prisen (2014)
Nettstedet www.cs.cmu.edu/~dwoodruf/

David P. Woodruff , født 1980, er førsteamanuensis ved School of Computer Science ved Carnegie-Mellon University . Han jobber med kompleksiteten i kommunikasjon, dataflytealgoritmer og deres nedre grenser, grafalgoritmer, maskinlæring, digital lineær algebra, skissemetoder.

Han oppnådde en doktorgrad i informatikk fra Massachusetts Institute of Technology i 2007 under veiledning av Piotr Indyk med en avhandling med tittelen Effektiv og privat avstandstilnærming i kommunikasjons- og streamingmodeller og ble deretter med i IBM Almaden Research Center . I andre semester 2018 er han også gjesteforsker ved Simons Institute for Theory of Computing  (en) .

Han ble tildelt Presburgerprisen i 2014 mens han fortsatt jobbet ved IBM Almaden Research Center i San Jose.

Virker

Woodruff ga viktige bidrag til dataflytsteorien, opprettet nye algoritmer og demonstrerte at noen algoritmer ikke kan eksistere. Hans arbeid påvirker andre områder, inkludert komprimert oppkjøp , maskinlæring og digital lineær algebra .

Innen dataflyten løste han det såkalte "  Distinct Elements Problem  " ved samtidig å optimalisere mengden minne som ble brukt, tiden som trengs for å behandle hver nye enhet og tiden som trengs for å presentere et estimat på antall 'separate elementer i bekken.

Innen maskinlæring brukte han sine tidligere resultater på datastrømmer til å designe sublinjære algoritmer for det lineære klassifiseringsproblemet og det minste sirkelproblemet .

I digital lineær algebra utviklet han de første tilnærmings- og regresjonsalgoritmer med lavere orden som opererer over tid i forhold til antall ikke-null oppføringer i inngangsmatrisen. Hans arbeid har også gitt patenter på datastrømmer og deres applikasjoner.

Han publiserte en lang artikkel som presenterte de problematiske skissene ( skissering ).

Merknader og referanser

  1. David Woodruff på katalogen Carnégie-Mellon University.
  2. Personlig side av David P. Woodruff
  3. (in) "  David P. Woodruff  " på nettstedet Mathematics Genealogy Project
  4. Den oppgaven Woodruff er tilgjengelig på sin personlige side.
  5. Divid Woodruff besøkende forsker.
  6. Presburger Award 2014
  7. Daniel M. Kane , Jelani Nelson og David P. Woodruff , "  En optimal algoritme for de forskjellige elementproblemet  ", PODS '10 Proceedings of the tenty-nende ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems ,2010, s.  41-52 ( DOI  10.1145 / 1807085.1807094 ).
  8. Kenneth L. Clarkson , Elad Hazan og David P. Woodruff , “  Sublinear optimization for machine learning,  ” Journal of the ACM , vol.  59, n o  5,2012, s.  1–49 ( ISSN  0004-5411 , DOI  10.1145 / 2371656.2371658 ).
  9. Den endelige versjonen av artikkelen som ble presentert i 2010 til FOCS vant Pat Goldberg Best Paper Award fra IBM.
  10. Kenneth L. Clarkson og David P. Woodruff , “  Low rank approximation and regression in input sparsity time  ”, STOC '13 Proceedings of the forty-five annual ACM symposium on Theory of computing , 2013, s.  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, n bein  1-2,2014, s.  1-157 ( les online )

Eksterne linker