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