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 on-line on his home-page. Work on Monte-Carlo 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 Small-World networks, on Resource Discovery in Distributed Networks, on a Directed Model of Web-Graphs 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 out-reach component. Together with Danny Sleator, the P.I. runs a popular puzzle page: www.cs.cmu.edu/puzzle/
