The central theme will be the relationship between logic and probabilistic techniques in the study of finite structures. In one direction, this topic includes recent research on limit laws and zero-one laws. A limit law holds in a class of finite structures if all properties decribable in some logical language have limiting probabilities as structure size grows; a zero-one law holds (as in the classic work of Glebskii et. al. and Fagin) 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 optimization problems. In the other direction, this topic covers use of probabilistic methods to establish lower bounds in circuit complexity. Particular emphasis will be placed on the connections between first-order logic and constant depth circuits with unbounded fan-in. While there will be natural connections to the workshop on "Descriptive complexity and finite models", here calculation of probabilities has center stage.
Presentations will be selected by the organizers.
Next: Call for Participation
Workshop Index
DIMACS Homepage