clarke@utcsri.UUCP (Jim Clarke) (01/16/87)
CANCELLED: Graphics Seminar on Thursday, January 22 at 10 am
(by Dr. Austin Henderson on ``Rooms'')
THEORY SEMINAR, Thursday, January 22, 3 pm, GB220
Professor Merrick Furst
Carnegie-Mellon University
``PSPACE Computations Survive Three-Bit Bottlenecks"
Constant-depth Boolean circuits play an important role when studying
the differences between the levels of the polynomial-time hierarchy and
PSPACE. The constant-width branching program model has always seemed to be
related in an intimate way with with the constant-depth circuit model.
This relationship leads to a curious question: ``Is there a natural hierar-
chy between P and PSPACE which is to constant-width branching programs as
the polynomial hierarchy is to constant-depth circuits?" The answer is
yes.
Remarkably, the new hierarchy collapses at its third level and by so
doing gives insight into the nature of PSPACE computations.
The new algebraic tools of Razborov and Smolensky have begun to have
application to the study of branching program complexity. While not
directly related to the first part of this talk, this topic is so poten-
tially interesting that I'll devote part of my time to discussing some
recent insights and progress.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke