bor@ai.toronto.edu ("A. Borodin") (11/07/88)
Mike Sipser will be here the week of Dec 5. Here is an abstract for his
lectures. Sipser is am excellent lecturer.
Applying the Infinite in Complexity Theory
Michael Sipser
Math Dept
MIT
Problems in complexity theory often concern the asymptotic
behavior of finite objects as their size grows. Sometimes we
may be able to gain insight into this behavior by examining
limiting objects of infinite size. In these talks we will present
two applications of this idea.
I. Analytic sets as an analog to NP.
It is easily seen that the NP sets are given by nondeterministic
depth two circuits of polynomial size. If we take instead circuits
of countably infinite size, the we get what are commonly called
the Analytic sets. We will give a new combinatorial proof of the
classical theorem that the Analytic sets are not closed under complement.
This proof may suggest a way to pursue the NP =? co-NP problem.
II. The Gabber-Galil explicit construction of expander graphs.
Expanders are a type of graph with numerous applications. It is easy
to see that they exist using a probabilistic argument. A number of
people have given explicit constructions for these graphs, generally
using sophisticated methods. The method of Gabber-Galil is to first
give a explicit construction of a type of infinite expander graph and
then use this to get a construction for finite graphs. We will give
a self-contained, accessible presentation of their proof.