Sunday, July 12

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
Program Program Overview Program-at-a-Glance Program Updates Speaker Index Registration Hotel Transportation

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