Description: 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.
A limited number of presentations have been solicited by the organizers. Additional presentations are not being solicited, in order to leave ample time for informal discussions.
Attendance at the workshop is open to all. To register, contact Pat Toci [toci@dimacs.rutgers.edu, (908) 445-5930]. If possible, please register beforehand, although registration at the conference is permitted. There is no registration fee.
Previous: Announcement
Next: Program
Workshop Index
DIMACS Homepage