CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
FriezeFest 2005
Related Activities
Outreach Roadshow

21-22 October 2005
McConomy Auditorium - University Center
Carnegie Mellon University, Pittsburgh, PA

Online Registration Form

Description: Frieze Fest 2005 is a workshop to honor and celebrate the career of Alan Frieze on the occasion of his 60th birthday. Professor Frieze played a central and leading role in the rapid development of the fields of randomized algorithms, random structures and combinatorics over the last three decades. This role has been recognized with a Fulkerson Prize, a Guggenheim Fellowship, and editorship in numerous leading journals in these areas. Given the central role professor Frieze has played, we expect this workshop to be a tremendous opportunity for interaction and dissemination across the fields of Discrete Mathematics, Operations Research and Theoretical Computer Science.

Banquet: On the evening of Friday, 21 October 2005, there will be a workshop banquet featuring reminiscences about the life and career of Alan Frieze (both respectful and otherwise). This banquet will be held at the elegant Pittsburgh Golf Club in Schenley Park. Light appetizers and a full sit-down dinner are included in the banquet fee; a cash bar will be available. The organizers strongly encourage all workshop participants to attend the banquet since it promises to be an enjoyable evening with good food and an entertaining social program. (Dress is business casual; please no t-shirts, jeans, shorts, or sneakers.)

Tom Bohman, Carnegie Mellon University, Tel 412-268-6881
Mike Molloy, University of Toronto, Tel 416-978-1932
R. Ravi, Carnegie Mellon University, Tel 412-268-3694


National Security Agency
Department of Mathematical Sciences
Tepper School

Registration and Payment Information: Late Registration Deadline Monday, October 17th
Registration is required. Anyone planning to attend the workshop and/or banquet (including CMU faculty and students) should register online.
Workshop:The fee to attend the workshop sessions is US$50; this fee will be waived for attendees who register by Friday, October 7th, 2005. Your registration fee includes admission to all workshop sessions, continental breakfast, lunch, and morning and afternoon coffee breaks.
Banquet: The additional fee to attend the banquet is US$30 for faculty and US$15 for students. This fee includes light appetizers and a full sit-down dinner; a cash bar will be available.
Online Registration Form

Hotel Accommodations
Out-of-town visitors should make hotel reservations immediately since availability is severely limited due to the University of Pittsburgh's homecoming. The Wyndham Garden Hotel (3454 Forbes Avenue, Pittsburgh, PA 15213) has agreed to extend the pre-negotiated rate of $145 per night ($165.30 including taxes) to workshop attendees as long as rooms are available. Parking is available in the hotel garage for an additional $12 per night ($13.68 including taxes). To make your reservations, you should call the Wyndham directly at 412-683-2040 and be sure to ask for the FriezeFest meeting rate.

Graduate Student and Postdoc Funding
Travel funding is available for a limited number of graduate students and/or postdocs who will be attending the workshop. This funding is restricted to US citizens and permanent residents. To apply, send a description of your research interests and one brief letter of support (preferably from an academic advisor) to Tom Bohman at Applications for this funding must be received by Friday, September 30, 2005. Travel awards will be in the form of room (3 nights stay in a shared hotel room) and up to $300 for airfare.

Getting Around Pittsburgh
Ground transportation between the airport and the Wyndham Garden Hotel or Carnegie Mellon (pdf)
Directions and map from the Wyndham Garden Hotel to Carnegie Mellon University and the Pittsburgh Golf Club (pdf)
Carnegie Mellon Campus Map (offsite link)
Yahoo! map and driving directions from Carnegie Mellon University to the Omni William Penn Hotel (pdf)

Agenda     Read the Abstracts    See the Poster (pdf 8.1MB), (gif 183KB)
Friday, 21 October 2005    Saturday, 22 October 2005
8:30 am Continental Breakfast
9:00 am

Noga Alon, Tel Aviv University
The Frieze-Kannan Decomposition method and Grothendieck type inequalities (abstract)

10:00 am Break
10:30 am

Jeff Kahn, Rutgers University
Some correlation inequalities (abstract)

11:05 am

Mike Steele, University of Pennsylvania
Minimum Spanning Trees and the Zeta Theorems (abstract)

11:40 am

Boris Pittel, Ohio State University
Bootstrap percolation on the random regular graph (abstract)

12:15 pm Lunch
2:00 pm

Ravi Kannan, Yale University
Low-Rank Approximations to Matrices and Tensors (abstract)

3:00 pm Break
3:30 pm

Colin Cooper, King's College London
The cover time of random walks on random graphs (abstract)

4:05 pm

Aravind Srinivasan, University of Maryland
The Local Lemma for random variables with large support (abstract)

4:40 pm

Eric Vigoda, Georgia Institute of Technology
Simulated Annealing for the Permanent and Binary Contingency Tables (abstract)

5:15 pm Free time / Travel to Banquet
6:30 pm Banquet
Cocktail hour begins at 6:30pm, with dinner beginning at 7:30pm.
Saturday, 22 October 2005   Friday, 21 October 2005
8:30 am Continental Breakfast
9:00 am

Eli Upfal, Brown University
The Combinatorics of Sequencing by Hybridization (abstract)

10:00 am Break
10:30 am

Dimitris Achlioptas, Microsoft Research
Clustering of solutions in random constraint satisfaction problems (abstract)

11:05 am

Andrei Broder, Yahoo! Research
Sampling Search Engine Results (abstract)

11:40 am

Richard M. Karp, University of California at Berkeley
Geometric Optics, Linear Programming and Congestion in Sensornets (abstract)

12:15 pm Lunch
1:30 pm

FOCS 2005 Tutorials
Separate registration is required for FOCS at

4:00 pm

Martin Dyer, University of Leeds
Generating random colourings (abstract)

5:00 pm

Nick Wormald, University of Waterloo
On the chromatic number of random regular graphs (abstract)

5:30 pm -
6:00 pm

Jeong Han Kim, Microsoft Research
Poisson Cloning Model and Giant Component of Random Graphs (abstract)


This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation