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