Alan Frieze

About

Alan Frieze is a Professor of Mathematical Sciences at Carnegie Mellon University, holding the title of University Professor. His research interests are in Probabilistic Combinatorics and its applications to Theoretical Computer Science and Operations Research. Much of his work has focused on the properties of random graphs, including studying the threshold for the occurrence of various properties in several models of a random graph. He has also investigated the expected performance of algorithms on random data, often involving random graphs, and has utilized Markov Chains as a computational tool. His contributions include work on estimating the volume of convex bodies in high dimensions, developing a randomized approximation scheme in collaboration with colleagues, and studying the number of proper k-colorings of graphs and hypergraphs. Frieze has extensively researched random walks in graphs, cover times of random graph models, and methods for finding edge and vertex disjoint paths in expander graphs. His recent work extends these studies to random hypergraphs and matroids. He has authored a book titled 'Introduction to Random Graphs' and has received numerous awards, including a Simons Foundation Fellowship, fellowship of the American Mathematical Society, SIAM Fellowship, and recognition as a plenary speaker at the 2014 International Congress of Mathematicians.

Research topics

• Combinatorics
• Mathematics
• Discrete mathematics
• Computer science
• Algorithm

Selected publications

• O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold

  2024-10-27 · 3 citations

  articleSenior author

  The random walk d-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk d-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xl…

  PublisherDOI

• The Bright Side of Simple Heuristics for the TSP

  The Electronic Journal of Combinatorics · 2024-10-03 · 3 citations

  articleOpen access1st authorCorresponding

  The greedy and nearest-neighbor TSP heuristics can both have $\log n$ approximation factors from optimal in worst case, even just for $n$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed $d$-Ahlfor's regular metric space (which includes any $d$-manifold like the $d$-cube $[0,1]^d$ in the case $d$ is an integer but also fractals of dimension $d$ when $d$ is real-value…

  PublisherOA PDFDOI

• Some online Maker-Breaker games

  Discrete Mathematics · 2025-02-19 · 1 citations

  articleSenior author
  PublisherDOI

• Rainbow Greedy Matching Algorithms

  Springer optimization and its applications · 2024-10-29 · 1 citations

  book-chapterSenior author
  PublisherDOI

• Diffusion limited aggregation in the layers model

  Journal of Applied Probability · 2026-04-28

  preprintOpen accessSenior authorCorresponding

  Abstract In the classical model of diffusion limited aggregation (DLA), introduced by Witten and Sander, the process begins with a single-particle cluster placed at the origin of a space. Then, one at a time, particles make a random walk from infinity until they halt by colliding with the existing cluster. We consider an analogous version of this process on large but finite graphs with a designated source and sink vertex. Initially the cluster of halted particles contains a single particle at th…

  PublisherOA PDFDOI

Recent grants

• Random Structures and Algorithms

  NSF · $330k · 2020–2025

• Random Structures and Algorithms

  NSF · $270k · 2017–2020

• Probabilistic Considerations in the Analysis of Algorithms

  NSF · $200k · 2005–2008

Frequent coauthors

• Colin Cooper

  154 shared

• Wesley Pegden

  91 shared

• Tom Bohman

  77 shared

• Andrzej Dudek

  Warsaw University of Technology

  58 shared

• Martin Dyer

  54 shared

• Miklós Ruszinkó

  Alfréd Rényi Institute of Mathematics

  43 shared

• Michael Krivelevich

  42 shared

• Michael Anastos

  Institute of Science and Technology Austria

  39 shared

Education

• Ph.D.

  University of London

Awards & honors

• Simons Foundation Fellowship
• Fellow of the American Mathematical Society
• SIAM Fellow
• Plenary speaker at the 2014 International Congress of Mathem…

Similar researchers at Carnegie Mellon University

• Michael Youngh-57
• David Kinderlehrerh-45
• Irene Fonsecah-42