### Sunday, July 12

## MS2

Logic and Random Structures

10:30 AM-12:30 PM

*Room: Sidney Smith 2110*

The central theme of this minisymposium will be the relationship between logic and probabilistic techniques in the study of finite structures. The speakers will address the behavior of limit probabilities for different languages and structures and the use of probabilistic methods to establish lower bounds in circuit complexity. This includes recent research on limit laws and zero-one laws. A limit law holds in a class of finite structures if all properties describable in some logical language have limiting probabilities as structure size grows; a zero-one law holds if the limiting probabilities are always 0 or 1. This work has been applied to areas such as analysis of algorithms for database query optimization and polynomial time approximation of NP complete optimization problems.

**Organizers: James F. Lynch **

*Clarkson University*

**Katherine St. John**

*Santa Clara University*

**10:30 Smoothness Laws for Random Ordered Graphs**
*Ravi B. Boppana* and Joel H. Spencer, Courant Institute of Mathematical Sciences, New York University
**11:00 On the Evolution of Random Structures**
- Gregory L. McColm, University of South Florida
**11:30 Semigeneric Models and ***0*-*1* Laws
- John T. Baldwin, University of Illinois, Chicago
**12:00 Characterizing the Limit Probabilities of the First Order Properties of Graphs**
- Joel H. Spencer, Courant Institute of Mathematical Sciences, New York University; and
*Lubos Thoma*, Institute for Advanced Study, Princeton

*LMH, 2/23/98; MMD, 5/29/98*