stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz) (02/26/91)
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.