Mikkel Thorup | |
---|---|

Born | 1965 (age 54–55) Denmark |

Alma mater | Oxford University, Technical University of Denmark |

Scientific career | |

Fields | Computer Science |

Institutions | AT&T Labs |

Thesis | Topics in computation (1994) |

Doctoral advisor | William F. "Bill" McColl Colin McDiarmid |

**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] }

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] }

- 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.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. S2CID 1713091.CS1 maint: ref=harv (link) 2011 MAA Robbins Award.

**Edsger Wybe Dijkstra** was a Dutch computer scientist, programmer, software engineer, systems scientist, science essayist, and pioneer in computing science. A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum (Amsterdam) from 1952 to 1962. A university professor for much of his life, Dijkstra held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin from 1984 until his retirement in 1999. He was a professor of mathematics at the Eindhoven University of Technology (1962–1984) and a research fellow at the Burroughs Corporation (1973–1984). In 1972, he became the first non-American, non-British, and continental European winner of the Turing Award.

A **minimum spanning tree** (**MST**) or **minimum weight spanning tree** is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a **minimum spanning forest**, which is a union of the minimum spanning trees for its connected components.

In graph theory, the **shortest path problem** is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

**Dijkstra's algorithm** is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In the mathematical field of graph theory the **Hamiltonian path problem** and the **Hamiltonian cycle problem** are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

In the mathematical subfield of graph theory a **level structure** of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex.

**Linear probing ** is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel and first analyzed in 1963 by Donald Knuth.

In graph theory, **reachability** refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex if there exists a sequence of adjacent vertices which starts with and ends with .

Prof. **Athanasios K. Tsakalidis** is a Greek computer scientist, a professor at the Graphics, Multimedia and GIS Laboratory, Computer Engineering and Informatics Department (CEID), University of Patras, Greece.

**Kurt Mehlhorn** is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.

In computer science, **streaming algorithms** are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes. In most models, these algorithms have access to limited memory. They may also have limited processing time per item.

**Michael John Fischer** is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.

In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the **transdichotomous model** is a variation of the random access machine in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman and Dan Willard, who chose its name "because the dichotomy between the machine model and the problem size is crossed in a reasonable manner."

In computer science, a family of hash functions is said to be ** k-independent** or

In computer science, **integer sorting** is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are.

In computer science, **tabulation hashing** is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; later work by Carter and Wegman extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings.

**Mihai Pătraşcu** was a Romanian-American computer scientist at AT&T Labs in Florham Park, New Jersey, USA.

In combinatorial mathematics and theoretical computer science, **heavy path decomposition** is a technique for decomposing a rooted tree into a set of paths. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants. The selected edges form the paths of the decomposition.

In computing, a **distance oracle (DO)** is a data structure for calculating distances between vertices in a graph.

In graph theory, a branch of mathematics, a **map graph** is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, but are more general. Any number of regions can meet at a common corner, and when they do the map graph will contain a clique connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices. Another example of a map graph is the king's graph, a map graph of the squares of the chessboard connecting pairs of squares between which the chess king can move.

- ↑ Mathematics genealogy project
- ↑ Thorup’s personal home page
- 1 2 Robbins Prize Citation
- ↑ Pătraşcu & Thorup 2011.
- ↑ Regan, Tabulation hashing and independence, Gödel’s Lost Letter, April 14, 2012, Fortnow, Complexity year in review, December 29, 2011.
- ↑ JACM editorial board Archived 2012-04-28 at the Wayback Machine
- ↑ ACM Fellows web site Archived 2012-05-27 at the Wayback Machine
- ↑ AT&T profile page for Mikkel Thorup
- ↑ Paterson et al. 2009.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.