### DIMACS Workshop on Logic and Random Structures

#### November 5 - 7, 1995

Rutgers University, DIMACS Center, Piscataway, NJ

**Organizers:**
**Ravi Boppana**, NYU, boppana@cs.nyu.edu
**James Lynch**, Clarkson University, jlynch@sun.mcs.clarkson.edu
**Kevin Compton**, University of Michigan, kjc@eecs.umich.edu

Presented under the auspices of the DIMACS Special Year on Logic and Algorithms.

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

Contacting the Center

Document last modified on May 5, 1995