selman@dara350j.ccs.northeastern.EDU (alan selman) (02/09/90)
Preliminary Program
Fifth Annual Structure in Complexity Theory Conference
8-11 July 1990,
Universitat Polit\`ecnica de Catalunya,
Barcelona, Spain
Note: Informal Rump Sessions will be scheduled at the end of each
day's formal session.
Sunday, July 8, Morning
Chair: Alan Selman, Northeastern University
8:45-9:30 On Polynomial Bounded Truth-Table Reducibility of NP Sets
to Sparse Sets,M. Ogiwara and O. Watanabe,
Tokyo Institute of Technology
9:40-10:25 Structural Properties of Nondeterministic Complete Sets,
S. Homer, Boston University
10:25-10:55 Break
10:55-11:25 On Sets with Efficient Implicit Membership Tests,
L. Hemachandra, University of Rochester, A.Hoene,Technische
Universit\"at Berlin,
11:30-12:00 On the Instance Complexity of NP-Hard Problems,
P. Orponen, University of Toronto and University of
Helsinki
Sunday, July 8, Afternoon.
Chair: Peter Clote, Boston College
1:30-2:15 Email and the Unexpected Power of Interaction (Tentative),
L. Babai, University of Chicago and Eotvos University
2:25-2:55 On Bounded Round Multi-Prover Interactive Proof Systems,
J. Cai, L. Lipton, Princeton University, A. Condon, University of
Wisconsin-Madison
3:00-3:30 Privacy, Additional Information, and Communication,
R. Bar-Yehuda, B. Chor, E. Kushilevitz, Technion
3:30-4:00 Break
4:00-4:30 On the Power of Randomness in the Decision Tree Model,
P. Hajnal, Princeton University and University of Szeged
4:35-5:05 On Read-Once Threshold Formulae
and their Randomized Decision Tree Complexity,
R. Heiman, Weizmann Institute, I. Newman, A. Wigderson,
Hebrew University
Monday, July 9, Morning
Chair: L\'aszl\'o Babai, University of Chicago and Eotvos
University
8:45-9:30 The Computational Complexity of Universal Hashing,
Y. Mansour, N. Nisan, M.I.T., P. Tiwari, IBM T.J. Watson
Research Center
9:40-10:25 Perfect Hashing, Graph Entropy, and Circuit Complexity,
I. Newman, A. Wigderson, Hebrew University,
P. Ragde, University of Waterloo
10:25-10:55 Break
10:55-11:25 Lower Bounds on Random-Self-Reducibility,
J. Feigenbaum, AT\&T Bell Laboratories, S. Kannan,
University of California-Berkeley, N. Nisan, M.I.T.
11:30-12:00 Non-Uniform Complexity Classes and Random Languages,
M. Mundhenk, Universit\"at Ulm, R. Schuler, U. Koblenz
Monday, July 8, Afternoon
Chair: Steven Homer, Boston University
1:30-2:15 Circuit Size Relative to Pseudorandom Oracles,
J. Lutz, W. Schmidt, Iowa State University
2:25-2:45 A Note on Relativizing Complexity
Classes with Tally Oracles,
L. Hemachandra, University of Rochester, R. Rubinstein,
Worcester Polytechnic Institute
2:50-3-20 An Oracle Separating \oplus P from PP(PH),
F. Green, Clark University
3:20-3:50 Break
3:50-4:20 On Separating Complexity Classes,
R. Book, University of California-Santa Barbara
4:25-4:55 Complexity Classes with Advice,
J. K\"obler, T. Thierauf, Universit\"at Ulm
Tuesday, July 10, Morning
Chair: Walter L. Ruzzo, University of Washington
8:45-9:30 A Survey of Counting Classes,
G. Wechsung, Friedrich-Schiller Universit\"at
9:40-10:25 A Very Hard Log Space Counting Class,
C. \`Alvarez, Universitat Polit\`ecnica de Catalunya,
B. Jenner, Universit\"at Hamburg
10:25-10:55 Break
10:55-11:25 The Boolean Hierarchy and the Polynomial Hierarchy:
A Closer Connection,
R. Chang, Cornell University, J. Kadin, University of Maine
11:30-12:00 On Read-Once vs. Multiple Access to Randomness in Logspace,
N. Nisan, M.I.T.
Tuesday, July 10, Afternoon
Chair: Gerd Wechsung, Friedrich-Schiller Universit\"at
1:30-2:15 Bounded Arithmetic and Complexity,
P. Clote, Boston College
2:25-2:55 Extensions to Barrington's M-Program Model,
F. B\'edard, F. Lemieux, P. McKenzie, Universit\'e de
Montr\'eal
3:00-3:30 The Quantifier Structure of Sentences that Characterize
Nondeterministic Time Complexity,
J. Lynch, Clarkson University
3:30-4:00 Break
4:00-4:30 Circuits, Pebbling, and Expressibility,
E. Vinay, C. Madhaven, Indian Institute of Science,
H. Venkateswaran, Georgia Institute of Technology
Wednesday, July 11, Morning
Chair: Dexter Kozen, Cornell University
8:45-9:30 Cheatable, P-Terse, and P-Superterse Sets,
A. Amir, W. Gasarch, University of Maryland, R. Beigel, Yale
University
9:40-10:25 Quantifiers and Approximation,
A. Panconesi, D. Ranjan, Cornell University
10:25-10:55 Break
10:55-11:25 Impossibilities and Possibilities
of Weak Separation Between NP and Exponential Time,
G. Lischke, Friedrich-Schiller Universit\"at
11:30-12:00 P-Productivity and Polynomial Time Approximations,
J. Wang, Boston University
Wednesday, July 11, Afternoon
Chair: Stuart Kurtz, University of Chicago
1:30-2:15 Title to be Announced (Tentative),
W. Ruzzo, University of Washington
2:25-2:45 Width-Bounded Reducibility and Binary Search over
Complexity Classes, E. Allender, Rutgers University,
C. Wilson, University of Oregon
2:50-3:20 Unambiguity of Circuits, K. Lange, Technische Universit\"at
M\"unchen
If you would like a latex source version of this announcement
please send a message to selman@corwin.ccs.northeastern.edu