Mikkel Thorup (born 1965) is a Danishcomputer scientist working 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]
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 has been editor of the area algorithm and data structures for Journal of the ACM, and has also served 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.[6] 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.”[7]
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.[8] “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] In 2021 he was co-winner of the Fulkerson Prize for his work with Ken-Ichi Kawarabayashi on fast deterministic algorithms for edge connectivity. [9]
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. S2CID 207654795. 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. S2CID 8324376. 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..
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. S2CID 1713091. 2011 MAA Robbins Award.
mikkel, thorup, born, 1965, danish, computer, scientist, working, university, copenhagen, completed, undergraduate, education, technical, university, denmark, doctoral, studies, oxford, university, 1993, from, 1993, 1998, university, copenhagen, from, 1998, 20. Mikkel Thorup born 1965 is a Danish computer scientist working 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 amp 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 ThorupBorn1965 age 58 59 DenmarkAlma materOxford University Technical University of DenmarkScientific careerFieldsComputer ScienceInstitutionsUniversity of CopenhagenThesisTopics in computation 1994 Doctoral advisorWilliam F Bill McCollColin McDiarmidThorup 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ătrascu 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 has been editor of the area algorithm and data structures for Journal of the ACM and has also served 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 6 He belongs to the Royal Danish Academy of Sciences and Letters since 2006 In 2010 he was bestowed the AT amp T Fellows Honor for outstanding innovation in algorithms including advanced hashing and sampling techniques applied to AT amp T s Internet traffic analysis and speech services 7 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 8 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 In 2021 he was co winner of the Fulkerson Prize for his work with Ken Ichi Kawarabayashi on fast deterministic algorithms for edge connectivity 9 Selected publications edit nbsp Scholia has an author profile for Mikkel Thorup 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 S2CID 207654795 Announced at FOCS 1997 Pătrascu 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 S2CID 8324376 Preliminary version published in FOCS 2006 doi 10 1109 FOCS 2006 35 Pătrascu 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 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 S2CID 1713091 2011 MAA Robbins Award References edit Mathematics genealogy project Thorup s personal home page a b Robbins Prize Citation Pătrascu amp Thorup 2011 Regan Tabulation hashing and independence Godel s Lost Letter April 14 2012 Fortnow Complexity year in review December 29 2011 ACM Fellows web site Archived 2012 05 27 at the Wayback Machine AT amp T profile page for Mikkel Thorup Paterson et al 2009 Fulkerson Prize Announcement Retrieved from https en wikipedia org w index php title Mikkel Thorup amp oldid 1211536754, wikipedia, wiki, book, books, library,
