Below is the tentative schedule of the Research Program. Please check for changes and additions in the daily PCMI schedule. All lectures will be held in Wolfensohn Hall at 4:30 PM. The abstracts follow the schedule.

Thursday, July 20

Friday, July 21

Monday, July 24

Tuesday, July 25

Thursday, July 27

Monday, July 31

Tuesday, August 1

Phase Transitions in Computer Science, Part I and II
Jennifer Chayes and Christian Borgs, Microsoft

Phase transitions are abrupt changes in the global behavior of a system when an external parameter is varied. They are familiar phenomena in physical systems. But such behavior also occurs in many probabilistic models and even in some problems in theoretical computer science. In these talks, we will discuss phase transitions in several systems, including percolation -- a simple probabilistic model which undergoes a critical transition from a disordered to an ordered phase; satisfiability -- a canonical model in theoretical computer science which undergoes a transition from solvability to insolvability; and number partitioning -- an NP-hard problem in combinatorial optimization which undergoes a transition corresponding to the disappearance of perfect partitions.

Technically, phase transitions only occur in infinite systems. However, real systems and the systems we simulate are large, but finite. Hence the question of finite-size scaling: Namely, how does the critical transition behavior emerge from the behavior of large, finite systems? Our results on the percolation, satisfiability and partitioning models locate the critical windows of the transitions and establish features within these windows.

No prior knowledge of phase transitions, percolation, satisfiability or number partitioning will be assumed in these talks.

Enormous Integers in Real Life
Harvey Friedman, Ohio State.

We survey a number of innocent looking finite combinatorial theorems whose associated lower bounds are demonstrably enormous. Most of the lower bound results are stated in conventional terms. However, logic is needed to describe the higher levels of enormousness among the enormous. In these contexts, one can see an intimate relationship between the level of enormousness and the level of nonconstructivity in the proof. Contexts in order of increasing enormousness include:

The equation f(x_1,...,x_k) = f(x_2,....,x_k+1)
Estimates in Bolzano-Weierstrass
Walks in the lattice points
Specific finite trees
Algebraic approximations to algebraic sets
Divisibility in sets of integers
Blocks in finite sequences of k letters
The inequality |f(x_1,...,x_k)| <= min(x_1,...,x_k)
The inequality f(x_1,...,x_k) <= f(x_2,...,x_k+1)
Embeddings of finite trees
Finite unions of circles in the plane

Computation on groups. A bird's eye view.
Igor Pak, MIT

I will give a very biased review of recent theoretical results dealing with computation on groups. Problems include testing some properties of a group (whether the group is abelian, solvable, etc.) as well as recognition of the group (say whether the group is S_n). We will also talk a bit about generating random group elements in finite groups. The talk is designed for a general audience and should be accessible to most undergraduates.

The Zig-Zag Graph Product, and Elementary Construction of Expander Graphs.
Omer Reingold, AT&T and IAS

Expander graphs are combinatorial objects which are fascinating and useful, but seemed hard to construct. The main result we present is an elementary way of constructing them.

The essential ingredient is a new type of graph product, which we call the zig-zag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large one, its degree from the small one, and its expansion properties from both! Iteration yields simple explicit constructions of constant-degree expanders of arbitrary size, starting from one constant-size expander.

Crucial to our intuition (and simple analysis) of the properties of this graph product is the view of expanders as functions which act as "entropy wave" propagators --- they transform probability distributions in which entropy is concentrated in one area to distributions where that concentration is dissipated. In these terms, the graph product affords the constructive interference of two such waves.

No special background is assumed.

Joint work with Salil Vadhan and Avi Wigderson

Diophantine Equations in two-variables
Minhyong Kim, U. of Arizona

We will give an elementary survey of this subject with a discussion of explicit methods of solution, actual or conjectural. In particular, I will try to explain the motivation for an `effective Mordell conjecture.

Natural Proofs
Steven Rudich

This talk will tie together the topics of the last two weeks of the summer school - lower bounds and pseudorandomness. Its main motivation is trying to explain the failure so far to prove lower bounds on general circuits, despite success for a variety of restricted circuit models. It main result gives a formal framework which captures essentially all restricted lower bounds proved so far, together with "unlikely" consequences if the same framework could yield general lower bounds. In other words, it formally explains in what sense we need to develop new lower bound techniques.

Joint work with Sasha Razborov.

Chernoff type bounds for sum of dependent random variables and their applications in randomized algorithms
Van Vu, Microsoft

Large deviation results play a crucial role in the analysis of randomized algorithms and several other areas in both combinatorics and computer science. In this talk, we present several new concentration results for sums of dependent random variables or functions with large Lipschitz coefficients. The strenght of these results is indicated by the fact that they can be applied in several situations where standard tools such as Csernoff's or Azuma's or Talagrand's inequalites fail.

We will show how to use these results to analyze a randomized algorithm which finds a large matching in a uniform hypergraph.