Speaker: Ronald Fagin, IBM Almaden Research Center, San Jose, California
		       fagin@almaden.ibm.com

Tutorial Talk 1: Finite-Model Theory - a Personal Perspective

Tutorial Talk 2: Easier Ways to Win Logical Games


----------------------------------------------------------------------------

TITLE: Finite-Model Theory - a Personal Perspective

Finite-model theory is a study of the logical properties of finite
mathematical structures.  This talk gives an overview, including:

(1) Differences between the model theory of finite structures and infinite
structures.  Most of the classical theorems of logic fail for finite
structures, which gives us a challenge to develop new concepts and tools,
appropriate for finite structures.

(2) The relationship between finite-model theory and complexity theory.
Surprisingly enough, it turns out that in some cases, we can characterize
complexity classes (such as NP) in terms of logic, without using any notion
of machine, computation, or time.

(3) Zero-one laws.  There is a remarkable phenomenon, which says that
certain properties (such as those expressible in first-order logic) are
either almost surely true or almost surely false.

(4) Descriptive complexity.  Here we consider how complex a formula must be
to express a given property.

In recent years, there has been a re-awakening of interest in finite-model
theory.  One goal of this talk is to help "fan the flames" of interest, by
introducing the audience to this fascinating area.

---------------------------------------------------------------------------

TITLE: Easier Ways to Win Logical Games

The computational complexity of a problem is the amount of resources, such
as time or space, required by a machine that solves the problem.  The
descriptive complexity of a problem is the complexity of describing the
problem in some logical formalism.  There is an intimate connection between
the descriptive complexity and the computational complexity.  This
connection was first discovered by the speaker, who showed that the
complexity class NP coincides with the class of properties of finite
structures expressible in existential second-order logic (where we are
allowed to existentially quantify over not just points, as in first-order
logic, but also over relations).  The equivalence of questions in
computational and descriptive complexity holds the promise that techniques
from one domain can be brought to bear on questions in the other domain.

Essentially the only known technique for proving hardness (that is,
inexpressibility) results in descriptive complexity is to make use of games
on graphs played between two players.  The purpose of this talk is to
discuss some results and techniques that assist in the use of these games,
and in particular that make the task of proving inexpressibility results
easier.  Thereby, we can prove new and deeper inexpressibility results.
Our hope is that we can develop such a powerful toolkit that we can
eventually make a serious assault on such fundamental problems as the
question of whether NP = co-NP.