1989 — 1993 
Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Algorithms and Complexity With Concentration On Probabilistic Analysis @ CarnegieMellon University
The aim of this project is to analyse and develop algorithms (for NP hard problems) that have a high probability of success. Here, Success means solving the problem exactly or, in the case of optimization problems, to within a small margin of error. A second aim is to improve the complexity, and to extend the application, of a recently developed randomized algorithm for approximating the volume of convex bodies. Generally, graph theoretic problems, packing problems and integer programming will be studied in the context of parallel, as well as serial, algorithms. Pseudorandom inputs and randomized algorithms that use pseudorandom numbers will also be considered.

1 
1993 — 2008 
Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Probabilistic Considerations in the Analysis of Algorithms @ CarnegieMellon University
SUMMARY Intellectual Merit Probabilistic considerations arise in the analysis of algorithms in at least two important ways. First of all, in a randomized algorithm the outcomes of random events are used to determine the progress of the algorithm. Randomization is now a standard tool of the computer scientist. A second area of consideration is when the problem instances come from some probability distribution and one wants to understand the average performance of a particular algorithm, which is often far better than its worst case. Both aspects are extremely important and this proposal describes a number of problems in these two areas. Broader Impact Results from this work will be disseminated at scientic workshops and at seminars at other institutions, both nationally and internationally. Results obtained will be published in journals and conference proceedings. The P.I. takes care to ensure that all of his recent papers are available online on his homepage. Work on MonteCarlo Markov Chain analysis has an impact on Probability Theory and Sta tistical Physics. In addition the proposal will have an impact on education, mainly at the graduate level. The PI tries to embed the knowledge gained from his research into courses and tries to involve his graduate students (currently four of them) as much as possible in any research that he does. Sometimes the work involved is of such a nature that it can lead to meaningful summer projects for bright undergraduates. In such cases the P.I. has sought and will seek additional support from the NSF and Carnegie Mellon University. In the recent past the P.I. has supervised such projects on SmallWorld networks, on Resource Discovery in Distributed Networks, on a Directed Model of WebGraphs and on a Graph Version of Nim. In addition, the P.I. is actively involved in the NSF funded Aladdin project in the Computer Science Department at CMU and this has a signicant outreach component. Together with Danny Sleator, the P.I. runs a popular puzzle page: http://www.cs.cmu.edu/puzzle/

1 
1995 — 1999 
Kannan, Ravindran (coPI) [⬀] Cornuejols, Gerard Balas, Egon [⬀] Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Gig: Algorithms, Combinatorics & Optimization: An Interdisciplinary Ph.D. Program @ CarnegieMellon University
9509581 Balas The last half century has seen an increasing use of computers insolving the complex decision problems that arise in a modern society.The methods needed to solve many of these problems are a fusion of ideas from Mathematics, Computer Science and Operations Research, Linear Programming, Integer Programming and Combinatorial OptimizationTechniques are widely used in today's world. Problems of production, distribution, and allocation are routinely modeled in this way. New techniques drawing from developments in all three disciplines are needed to solve the ever larger problems that arise in a technologically advanced society. In addition, new areas of application emerge repeatedly. For example, the recent upsurge of activity in Computational Molecular Biology relies heavily on Discrete Mathematics to untangle the knotty sequencing problems that it throws up. The knowledge needed to solve such problems transcends the traditional boundaries of a modern university. Researchers in Mathematics, Operations Research and Computer Science Departments often find themselves working on similar problems. On the other hand the idea of training graduate students simultaneously in all three areas has been slow to get off the ground. Carnegie Mellon recognized this several years ago. Using it's internationally recognized strengths in all three areas it responded by setting up the Ph. D. program in Algorithms, Combinatorics and Optimization. A unique feature of the program is that students are given a thorough grounding in the foundations of all three areas before they embark on their research. Now nearly 30 students have taken part in the program. The quality of the students has been excellent and the first crop of graduates have taken up positions in major universities and research laboratories.The program has inspired other institutions to provide similar courses.The money from this grant will be used to support graduate students and to provide t hem with an environment in which they can acquire knowledge and research skills in all three areas.

1 
2008 — 2012 
Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Random Graphs: Structure and Algorithms @ CarnegieMellon University
ABSTRACT
Principal Investigator: Frieze, Alan Proposal Number: DMS  0753472 Institution: CarnegieMellon University Title: Random Graphs: Structure and Algorithms
The study of random combinatorial structures has emerged as an important component of Discrete Mathematics. The most intensely studied area is that of random graphs and many of the results of this area have been extended to hypergraphs or set systems. This proposal is aimed at doing research into various structural properties of random graphs and hypergraphs. In addition the proposal will consider some related algorithmic questions.
Graphs and networks are emerging as important phenomena. Networks arise in social contexts such as links between pages in the World Wide Web. They also arise in biological systems such as the protein interaction network of a cell. These networks arise from "random processes" and so the study of random graphs is becoming more and more relevant. Finally, studying algorithms on typical graphs will hopefully be usefull in drawing back the shadow of the negative results of complexity theory.

1 
2010 — 2014 
Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Af: Small: Probabilistic Considerations in the Analysis of Algorithms @ CarnegieMellon University
The aim of this project is to advance the understanding of various aspects of probability in relation to algorithm design and analysis. In general this means the study of randomized algorithms, the average case performance of algorithms and related, seemingly random, structures such as social networks. Randomized algorithms are important because they are often the most efficient and some times the only efficient way to solve computational problems. The study of the average case sheds light on why problems which in the worstcase seem computationally difficult or even intractable, can be routinely solved in practise, by simple algorithms. The research on random models of large real world networks is important for answering algorithmic questions about them and for understanding their evolution.
The project will study several important problems from the point of view of average case analysis: (i) Cuckoo Hashing is a relatively new hashing algorithm and some of the basic questions about its performance remain unanswered, even though there has been significant progress of late. (ii) The matching problem for graphs is the quintissential polynomial time solvable problem in Combinatorial Optimiztion. Its polynomial time solution is one of the great achievements of the area. Its worstcase complexity, while polynomial still leaves room for improvement and one of the aims of the project is to settle the average case completely. (iii) The hamilton cycle problem for graphs is one of the canonical NPhard problems. The averagecase complexity was reduced to polynomial time some time ago and one of the aims of the project is to reduce this to as close to expected linear time as possible. The project will also several other problems involving average case complexity. The methodology employed will involve the tools and techniques from the field of Random Graphs. The two main tools being concentration of measure and concentration on events that happen with probability close to one.
The project will also consider the use of Rapidly Mixing Markov Chains to generate random colorings of graphs and hypergraphs. This topic has close ties to Statistical Physics and has benefited a great deal from the crossfertilization of ideas. There are still many gaps, particularly in the case of hypergraphs, and the project aims to close them.
While graph theory is at least a hundred years old, it is only in recent years that the ubiquitousness of graphs or networks has been so widely recognized. The study of Random Graphs is about fifty years old and techniques from this area are needed to study real world networks. Simply because they evolve in a seemingly random manner. The project will involve several analyses from this area. For example, it is not known what is the component structure of a random graph, evolving under preferential attachment but subject to deletions.

1 
2011 — 2012 
Horn, Paul Frieze, Alan Pralat, Pawel 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
8th Workshop On Algorithms and Models For the Web Graph (Waw 2011) @ West Virginia University Research Corporation
The World Wide Web has become part of our everyday life, and information retrieval and data mining on the Web are now of enormous practical interest. The algorithms supporting these activities combine the view of the Web as a text repository and as a graph, induced in various ways by links among pages, hosts and users.
The aim of the 8th Workshop on Algorithms and Models for the Web Graph (WAW 2011) is to further the understanding of graphs that arise from the Web and various user activities on the Web, and stimulate the development of highperformance algorithms and applications that exploit these graphs. The workshop will also welcome the researchers who are working on graphtheoretic and algorithmic aspects of related complex networks, including citation networks, social networks, biological networks, molecular networks, and other networks arising from the Internet.
Web site: http://waw2011.math.wvu.edu/

0.934 
2014 — 2020 
Bohman, Tom Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Random Structures and Algorithms @ CarnegieMellon University
This research project is an investigation of discrete mathematical objects, like networks or codes, whose structure is generated randomly. Randomness has long played an important role in the construction of sophisticated mathematical objects and randomness plays a central role in many algorithms in computer science. Part of this research focuses on objects that are generated by a sequence of dependent random choices. Such processes can be good models for the dynamics of realworld phenomenon, like the spread of a disease in a network, the evolution of social networks such as facebook or twitter, or phase transitions in materials. We are particularly interested in the solution of challenging computational problems in the context of random structures, and this work will hopefully be useful in drawing back the shadow of the negative results of complexity theory.
The study of random combinatorial structures has emerged as an important component of Discrete Mathematics. This research project focuses on various structural properties of random graphs and hypergraphs. One area of emphasis is the study of the existence of Hamilton cycles in various sparse random graph models. It is natural to conjecture that any suitably random model that ensures that a graph has minimum degree 3 will have a Hamilton cycle with high probability. While this has been established in a few setting, a number of very natural open questions remain, and the development of a unified theory of Hamiltonicity of sparse random graphs is a long range goal of this research. This project also includes the study of algorithmic questions. For example, we will put significant effort into the study of Cuckoo hashing. Here the main question is whether or not the insertion of a new item into the hash table takes constant expected time. Our approach here will be to show that an associated graph has a fast mixing time, applying the theory of mixing times for Markov chains.

1 
2015 — 2017 
Frieze, Alan 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Af: Eager: Probabilistic Considerations in the Analysis of Algorithms @ CarnegieMellon University
One of the main uses for computers is to solve large computational problems of a discrete nature, for example to find ways of optimally routing vehicles to make deliveries within minimum time. To be useful, the amount of computing time needed to solve the problem must be small. Unfortunately, many, if not most of the problems of this nature tend to be of a class for which there is no algorithm that can finish quickly for all problem instances. On the other hand, these problems have to be tackled and it has been noted that algorithms tend to do better than the worstcase scenario might suggest.
Integer Programming is a framework within which many of these problems can be described. The PI will conduct research on the average performance of algorithms for these problems. The aim is twofold. First, the PI wants to explain, in terms of probability, why the average performance is much better than the worst case. Second, the PI will seek ways to practically exploit the ''friendly'' nature of typical problems, thus leading to more efficient algorithms for Integer Programming.
The related problem of Linear Programming has been a spectacular success for mathematics. The Simplex Algorithm and more recent Interior Point Method have enabled us to solve huge linear programs. Integer Programs are superficially similar to Linear Programs and one approach to solving them is through polyhedral methods. We try to approximate the convex hull of the integer solutions and then apply Linear Programming. This has led to the study of Polyhedral Combinatorics. The PI proposes to study Polyhedral Combinatorics within a probabilistic framework. For example, the PI will try to determine the expected number of Gomory cuts needed to solve a pure Integer Program. This will require a combination of probabilistic, geometric, and algorithmic ideas in order to be successful.

1 