Mikkel Thorup (born 1965) is a Danish

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

working at

University of Copenhagen The University of Copenhagen (, KU) is a public university, public research university in Copenhagen, Copenhagen, Denmark. Founded in 1479, the University of Copenhagen is the second-oldest university in Scandinavia, after Uppsala University. ...

. He completed his

undergraduate Undergraduate education is education conducted after secondary education and before postgraduate education, usually in a college or university. It typically includes all postsecondary programs up to the level of a bachelor's degree. For example, ...

education at

Technical University of Denmark The Technical University of Denmark (), often simply referred to as DTU, is a polytechnic university and school of engineering. It was founded in 1829 at the initiative of Hans Christian Ørsted as Denmark's first polytechnic, and it is today ran ...

and his doctoral studies at

Oxford University The University of Oxford is a collegiate research university in Oxford, England. There is evidence of teaching as early as 1096, making it the oldest university in the English-speaking world and the second-oldest continuously operating u ...

in 1993. 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). Thorup's main work is in

algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...

and

data structures In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...

. One of his best-known results is a linear-time algorithm for the single-source shortest paths problem in undirected graphs (Thorup, 1999).Robbins Prize Citation
/ref> With Mihai Pătraşcu he has shown that simple

tabulation hashing A table is an arrangement of information or data, typically in rows and columns, or possibly in a more complex structure. Tables are widely used in communication, research, and data analysis. Tables appear in print media, handwritten notes, comp ...

schemes achieve the same or similar performance criteria as hash families that have higher independence in worst case, while permitting speedier implementations. Thorup has been editor of the area algorithm and data structures for

Journal of the ACM The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...

, and has also served on the editorial boards of

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

, 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. He belongs to the

Royal Danish Academy of Sciences and Letters The Royal Danish Academy of Sciences and Letters ({{Langx, da, Det Kongelige Danske Videnskabernes Selskab or ''Videnskabernes Selskab'') is a Danish academy of science. The Royal Danish Academy was established on 13 November 1742, and was create ...

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.”AT&T profile page for Mikkel Thorup
/ref> In 2011 he was co-winner of the David P. Robbins Prize from the

Mathematical Association of America The Mathematical Association of America (MAA) is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university A university () is an educational institution, institution of tertiary edu ...

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. “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.” In 2021 he was co-winner of the Fulkerson Prize for his work with Ken-Ichi Kawarabayashi on fast deterministic algorithms for edge connectivity. Fulkerson Prize Announcement
/ref>

Selected publications

* Announced at FOCS 1997. * Preliminary version published in FOCS 2006, . *. * 2011 MAA Robbins Award.

References

{{DEFAULTSORT:Thorup, Mikkel Living people Danish computer scientists Theoretical computer scientists 2005 fellows of the Association for Computing Machinery 1965 births