Carnegie Mellon Today

Carnegie Mellon Today

Carnegie Mellon News Services Home Page

Carnegie Mellon Holds Workshop to Celebrate the Career of Influential Mathematician and Computer Scientist Alan Frieze

Alan Frieze
Scientists from around the world will visit Carnegie Mellon University to celebrate the remarkable career of Alan Frieze and present their latest research at Frieze Fest 2005. This workshop, which marks Frieze's 60th birthday, will be held Friday, Oct. 21, and Saturday, Oct. 22, at the University Center.

A professor of mathematical sciences, Frieze is widely acclaimed for his central role in the rapid advances in the fields of randomized algorithms, random structures and combinatorics over the last 30 years.

"Alan has been a leading force in probabilistic combinatorics and randomized algorithms, two fields that have grown in parallel," said Tom Bohman, associate professor of mathematical sciences and a workshop co-organizer.

"His work has made a significant impact in diverse activities such as optimizing business operations, improving information networking and developing computationally based medical diagnostics," said R. Ravi, professor of operations research and computer science, associate dean for intellectual strategy at the Tepper School of Business and workshop co-organizer.

The workshop provides a rare opportunity for interaction across the fields of discrete mathematics, operations research and theoretical computer science, according to the organizers. Presenters from Yale University, Microsoft Research, IBM, the University of California at Berkley, the University of Leeds and other institutions will share results of research inspired by the work of Frieze or done in collaboration with him.

Over the last 30 years, Frieze has made a series of fascinating discoveries in the area of discrete mathematics known as probabilistic combinatorics, which began with the pioneering work of Hungarian Paul Erdos. Probabilistic combinatorics considers the properties of discrete mathematical objects that are generated at random. These objects often have beautiful and surprising structures, according to Bohman.

By the 1980s, researchers realized that insights developed in the study of probabilistic combinatorics can be used to develop randomized algorithms to solve problems that arise in computer science. A randomized algorithm solves a problem by producing part of the solution at random or using randomness to guide the search for a solution.

"Research by Frieze has created key, versatile tools used for probabilistic combinatorics and randomized algorithms, thereby allowing scientists to advance both fields," said Bohman.

Randomized algorithms developed by Frieze have been used to solve several important questions in computer science, such as calculating the volume of a convex body. For this work, Frieze received the 1991 Fulkerson Prize for Discrete Mathematics with co-authors Dyer and Kannan.

Frieze's research has made a profound impact in many fields. In computer networking, he has analyzed schemes for dynamically routing packets in networks with bounded buffers. Another of his contributions, random graph modeling, is central to creating analytical models of Internet growth and activity. Frieze also is renowned for research on convergence rates of sampling processes, (work inspired by statistical physics) and work on average-case analysis of algorithms under typical random inputs.

Another field that has benefited from Frieze's research is computational medical diagnostics. Using algorithms developed by Frieze, scientists are currently trying to determine the minimum number of molecular probes needed on a DNA chip to identify and reconstruct DNA sequences. Such chips are used to diagnose a disease or monitor treatment.

Frieze received his bachelor's of science in mathematics from Oxford University and his doctorate in mathematics from London University. He is a past recipient of a Guggenheim Fellowship, and currently sits on the editorial boards of 12 journals, including Random Structures and Algorithms and Combinatorics, Probability and Computing. He has authored or co-authored more than 200 publications.

Carnegie Mellon University sponsors of Frieze Fest 2005 include the ALADDIN Center, the Department of Mathematical Sciences and the Tepper School of Business. The workshop also is supported in part by the National Security Agency.

For more information, visit

Lauren Ward
October 18, 2005

Carnegie Mellon Home