Alan Frieze
Orion Hoch, S 1952, University Professor of Mathematical Sciences
Address:
6204 Wean Hall
Department of Mathematical Sciences
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
P: 412-268-8476
F: 412-268-6380
Education
Ph.D., University of London
Awards
- Simons Foundation Fellowship
- Fellow of the American Mathematical Society
- SIAM Fellow
- Plenary speaker at the 2014 International Congress of Mathematicians
- Fulkerson prize
Research
My research interests are in Probabilistic Combinatorics and its application to Theoretical Computer Science and Operations Research. Much of my work has focused on the properties of random graphs and I have recently completed a book on the subject: Introduction to Random Graphs by A.M. Frieze and M. Karoński, Cambridge University Press, 2015.
My research has focused on finding the threshold for the occurrence of various properties in several models of a random graph. In addition I have studied the expected performance of algorithms on random data, often a random graph. I have worked on the use of Markov Chains as a computational tool. I worked on the problem of estimating the volume of a convex body in a large number of dimensions.
Together with my colleagues, Martin Dyer and Ravi Kannan, I was able to produce the first randomized approximation scheme for this problem. I have also worked on the problem of estimating the number of proper k-colorings of a graph or hypergraph.
I have several papers on random walks in graphs. I have studied the cover time of many models of random graphs and have used random walks to find edge/vertex disjoint paths in expander graphs.
I am currently working on extending much of my work on random graphs to random hypergraphs and to random matroids.
Select Publications
Frieze, A.M. (1985). On the value of a random minimum spanning tree problem. Discrete Applied Mathematics, 10, 47-56.
Frieze, A.M. (2001). Edge disjoint paths in expander graphs. SIAM Journal on Computing, 30, 1790-1801.
Frieze, A.M. (2004). On random symmetric travelling salesman problems. Mathematics of Operations Research, 29, 878-890.
Dyer, M.E., Frieze, A.M., and Kannan, R. (1991). A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the Association for Computing Machinery, 38 1-17.
Aronson, J., Frieze, A.M., and Pittel, B. (1998). Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Structures and Algorithms, 12, 111-178.
Bohman, T., and Frieze, A.M., (2009). Hamilton cycles in 3-out. Random Structures and Algorithms, 35, 393-417.
Chebolu, P., Frieze, A.M., and Melsted, P., (2010). Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. Journal of the Association for Computing Machinery, 57, 1-27.
Cooper, C., and Frieze, A.M. (2011). The cover time of random geometric graphs. Random Structures and Algorithms, 38, 324-349.
Bohman, T., Frieze, A.M., and Lubetzky, E. (2015). Random triangle removal. Advances in Mathematics, 280, 379-438.
Dudek, A., Frieze, A.M., Rucinski, A. and Siliekis, M., (2017). Embedding the Erdos-Renyi Hypergraph into the Random Regular Hypergraph and Hamiltonicity. Journal of Combinatorial Theore B, 719-740.
Frieze, A.M. and Pegden, W., (2017). Separating subadditive Euclidean functionals, Random Structures and Algorithms 51 375-403.
Chikina, M., Frieze, A.M., and Pegden, W. (2017). Assessing significance in a Markov chain without mixing. Proceedings of the National Academy of Sciences, 114, 2860-2870.