Mikkel Thorup

Mikkel Thorup (born 1965) is a Danish computer scientist jointly affiliated at AT&T Labs in Florham Park, New Jersey, United States and at University of Copenhagen. He completed his undergraduate education at Technical University of Denmark and his doctoral studies at Oxford University in 1993.[1] From 1993 to 1998, he was at University of Copenhagen and from 1998 to 2013 he was at AT&T Labs-Research in New Jersey. Since 2013 he has been at the University of Copenhagen as a Professor and Head of Center for Efficient Algorithms and Data Structures (EADS).[2]

Mikkel Thorup
Born1965 (age 54–55)
Denmark
Alma materOxford University, Technical University of Denmark
Scientific career
FieldsComputer Science
InstitutionsAT&T Labs
ThesisTopics in computation (1994)
Doctoral advisorWilliam F. "Bill" McColl
Colin McDiarmid

Thorup's main work is in algorithms and data structures. One of his best-known results is a linear-time algorithm for the single-source shortest paths problem in undirected graphs (Thorup, 1999).[3] With Mihai Pătraşcu he has shown that simple tabulation hashing schemes achieve the same or similar performance criteria as hash families that have higher independence in worst case, while permitting speedier implementations.[4][5]

Thorup is the editor of the area algorithm and data structures for Journal of the ACM.[6] He also serves on the editorial boards of SIAM Journal on Computing, ACM Transactions on Algorithms, and the Theory of Computing. He has been a Fellow of the Association for Computing Machinery since 2005 for his contributions to algorithms and data structures.[7] He belongs to the Royal Danish Academy of Sciences and Letters since 2006. In 2010 he was bestowed the AT&T Fellows Honor for “outstanding innovation in algorithms, including advanced hashing and sampling techniques applied to AT&T's Internet traffic analysis and speech services.”[8]

In 2011 he was co-winner of the David P. Robbins Prize from the Mathematical Association of America for solving, to within a constant factor, the classic problem of stacking blocks on a table to achieve the maximum possible overhang, i.e., reaching out the furthest horizontal distance from the edge of the table.[9] “The papers describe an impressive result in discrete mathematics; the problem is easily understood and the arguments, despite their depth, are easily accessible to any motivated undergraduate.” [3]

Selected publications
  • Thorup, Mikkel (1999). "Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. Announced at FOCS 1997.
  • Pătraşcu, Mihai; Thorup, Mikkel (2010). "Higher lower bounds for near-neighbor and further rich problems". SIAM Journal on Computing. 39 (2): 730–741. doi:10.1137/070684859. Preliminary version published in FOCS 2006, doi:10.1109/FOCS.2006.35.
  • Pătraşcu, Mihai; Thorup, Mikkel (2011). "The power of simple tabulation hashing". Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11). pp. 1–10. arXiv:1011.5200. doi:10.1145/1993636.1993638.CS1 maint: ref=harv (link).
  • Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri (2009). "Maximum overhang". The American Mathematical Monthly. 116 (9): 763–787. arXiv:0707.0093. doi:10.4169/000298909x474855.CS1 maint: ref=harv (link) 2011 MAA Robbins Award.
gollark: ?!?
gollark: ++exec```haskellimport Unsafe.Coercedata Would = Seriously Why Int deriving Showtype Mad = ()data Are = Are Mad deriving Showtype Is = Aredata You = You Are Mad deriving Showdata Thing = This Thing Is Mad deriving Showdata This = Thing Mad deriving Shownewtype Do = Do (Thing -> You -> [Thing])data Why = Why Would You Do This deriving Showinstance Show Do where show x = "Do the thing!"why :: Whywhy = Why would you do_ this where would = unsafeCoerce why you = You (Are ()) () do_ = Do $ \_ _ -> [] this = Thing ()main = print why```
gollark: Gooood.
gollark: ++exec```haskellimport Unsafe.Coercedata Would = Seriously Why Int deriving Showtype Mad = ()data Are = Are Mad deriving Showtype Is = Aredata You = You Are Mad deriving Showdata Thing = This Thing Is Mad deriving Showdata This = Thing Mad deriving Shownewtype Do = Do (Thing -> You -> [Thing])data Why = Why Would You Do This deriving Showinstance Show Do where show x = "Do the thing!"why :: Whywhy = Why would you do_ this where would = unsafeCoerce () you = You (Are ()) () do_ = Do $ \_ _ -> [] this = Thing ()main = print why```
gollark: It works!

References
  1. Mathematics genealogy project
  2. Thorup’s personal home page
  3. Robbins Prize Citation
  4. Pătraşcu & Thorup 2011.
  5. Regan, Tabulation hashing and independence, Gödel’s Lost Letter, April 14, 2012, Fortnow, Complexity year in review, December 29, 2011.
  6. JACM editorial board Archived 2012-04-28 at the Wayback Machine
  7. ACM Fellows web site Archived 2012-05-27 at the Wayback Machine
  8. AT&T profile page for Mikkel Thorup
  9. Paterson et al. 2009.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.