Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!linac!midway!midway.uchicago.edu!stuart
From: stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz)
Newsgroups: comp.theory
Subject: Theory Day at the University of Chicago
Message-ID:
Date: 25 Feb 91 16:01:06 GMT
Sender: news@midway.uchicago.edu (News Administrator)
Organization: Dept. of Comp. Sci., The University of Chicago
Lines: 58
Theory Day
March 9, 1991
The University of Chicago
The University of Chicago Department of Computer Science will be hosting a
theory day on Saturday, March 9, 1991, in cooperation with the 1991 IEEE
Structure in Complexity Conference. Talks will be given my members of the
Structures Program Committee. A free lunch will be provided. Talks will
be given in Kent 107.
10:00 Walter L. Ruzzo: Time-Space Tradeoffs for Undirected Graph Traversal
Graph traversal is a fundamental problem in computing, since it is the
natural abstraction of many search processes. In computational
complexity theory, graph traversal is a fundamental problem for an
additional reason: understanding the complexity of directed versus
undirected graph traversal seems to be the key to understanding the
relationships among deterministic, probabilistic, and nondeterministic
space-bounded algorithms.
11:00 Jose Balcazar: Some Results on Depth-Bounded Reducibilities
The talk will describe a computational model which allows us to
characterize, in several quite instructive ways, complexity classes
corresponding to fast feasible parallel computation (such as NC), as well
as the corresponding reducibilities. A new P-complete problem will also
be presented. This is joint work with Carme Alvarez, Birgit Jenner,
Joaquim Gabarro, and Miklos Santha.
12:00 Lunch, Eckhart 209.
1:00 William Gasarch: Recursion-theoretic Work on Bounded Queries--A Survey
If you could ask the halting problem THREE questions, than are you better
off then if you could only ask it only TWO? We ask, in a recursion
theoretic setting, for which sets A, are k queries to A more powerful
than k+1 queries. We also consider the relationship between parallel
(nonadaptive) and serial (adaptive) queries. It has been known for some
time that if A is nonrecursive, then to answer 2^n parallel membership
questions requires at lest n adaptive queries. Martin Kummer has
recently proved that that answering the apparently easier question of how
many of these 2^n arbitrary numbers are in A must also require at least n
adaptive queries.
2:00 Christos Papadimitriou: Inefficient Existence Proofs and Complexity
We point out that in several well-known instances in Mathematics the
existence of a mathematical object is established by a constructive
argument based on an exponentially large graph. These include Brouwer's
Fixpoint Theorem, the Borsuk-Ulam Theorem, the Arrow-Debreu theory in
mathematical economics, Chevalley's Theorem in number theory, the
convergence of Hopfield neural nets, Smith's Theorem in graph theory, and
many others. We show that this phenomenon can be captured by complexity
classes, containing several important complete problems.
Please contact Stuart Kurtz (stuart@cs.uchicago.edu) if you are planning to
attend---we need an approximate head count for the caterers.