arvind@utcsri.UUCP (Arvind Gupta) (03/23/87)
From: srm%btl.csnet@relay.cs.net
Subject: Structure in Complexity Theory Second Annual Conference
Structure in Complexity Theory
Second Annual Conference
Sponsored by the
IEEE Computer Society's Technical Committee on
Mathematical Foundations of Computing
In cooperation with ACM-SIGACT
June 16-19, 1987
Cornell University
Ithaca, NY 14853
--------------------------------------------------------------------------
Registration Fees: By June 1 After June 1
Members of:
IEEE-CS,
ACM, and Authors $150 $195
Nonmembers $190 $245
Full-time Students $50 $75
The housing costs and addresses to send registration fees are not available
at this time. A second theory-net announcement will include this information.
-------------------------------------------------------------------------------
Program for 2nd Structure in Complexity Theory Conference
Monday, June 15, 1987
Evening: Reception hosted by Mathematical Sciences Institute, Cornell
Tuesday, June 16, 1987
8:45 am. Lowness and Probabilistic Complexity Classes, Uwe Schoning,
EWH Koblenz
9:45 am. On Hiding Information from an Oracle, Martin Abadi, DEC-SRC,
Joan Feigenbaum, Bell Labs, and Joe Kilian, MIT
11:00 am. Complexity Characterizations of Attribute Grammar Languages,
Sophocles Ephremidis, Athens, Christos Papadimitriou, Athens and Stanford,
and Martha Sideris, Athens
11:45 am. Reversal Complexity, Jian-er Chen and Chee-Keng Yap, NYU
2:00 pm. Polynomial Terse Sets, Amihood Amir and William I. Gasarch, Maryland
2:45 pm. A Structural Theorem that Depends Quantitatively on the Complexity
of SAT, Richard Beigel, Johns Hopkins
NP[log n]
4:00 pm. P and Sparse Turing Complete Sets for NP, Jim Kadin, Cornell
4:45 pm. The Probabilistic Communication Complexity of Set Intersection,
Georg Schnitger and Balasubramanian Kalyanasundaram, Penn State
Wednesday, June 17, 1987
8:45 am. Near-Testable, P-Cheatable, and P-Terse Sets,
Judy Goldsmith, Deborah Joseph, Wisconsin, and Paul Young, Washington
9:45 am. Honest Polynomial Reducibilities, Recursively Enumerable Sets,
and the P=?NP Problem, Klaus Ambos-Spies, Dortmund
11:00 am. Unprovably Intractable Languages, Kenneth W. Regan, Cornell
11:45 pm. Resource Bounded Baire Category and Small Circuits in Exponential Spa
Jack H. Lutz, Caltech
2:00 pm. PSPACE Survives Three-Bit Bottlenecks, Jin-Yi Cai, Yale, and
Merrick L. Furst, CMU
2:45 pm. On Ranking, Lane A. Hemachandra, Cornell
4:00 pm. On Threshold Circuits and Polynomial Computation, John Reif, Duke
4:45 pm. Informal Talk Sessions
Evening Business Meeting
Thursday, June 18, 1987
8:45 am. One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete
Sets, Juris Hartmanis and Lane Hemachandra, Cornell
9:45 am. Strong Nondeterministic Reduction - A Technique for Proving
Intractability, Moon Jung Chung, RPI, and B. Ravikumar, Minnesota
11:00 am. Polynomial Time Reducibility to a Set of Small Density,
Osamu Watanabe, Tokyo Institute of Technology
11:45 pm. On Sets Reducible to Sparse Sets, Ronald V. Book, UC Santa
Barbara, and Ker-I Ko, SUNY Stony Brook
2:00 pm. The Complexity of Perfect Zero-Knowledge, Lance Fortnow, MIT
2:45 pm. Some Consequences of the Existence of Pseudorandom Generators,
Eric W. Allender, Rutgers
4:00 pm. Picnic and Barbecue
Friday, June 19, 1987
8:45 am. Progress on Collapsing Degrees, Stuart Kurtz, Chicago,
Stephen Mahaney, Bell Labs, and James Royer, Chicago
9:45 am. A Theory of Oracle Machines, Jonathan F. Buss, Waterloo
11:00 am. On Helping by Robust Oracle Machines, Ker-I Ko, SUNY Stony Brook
11:45 pm. The Strong Exponential Hierarchy Collapses, Lane A. Hemachandra,
Cornell
2:00 pm. Expressibility as a Complexity Measure: Results and Directions,
Neil Immerman, Yale
3:00 pm. Characterization of Complexity Classes in Higher-Order Logic,
Daniel Leivant, CMU
4:15 pm. Complexity Theoretic Algebra I - Vector Spaces over Finite Fields,
Anil Nerode, Cornell and J. B. Remmel, UC San Diego
5:00 pm. Informal Talks
The organizers wish to encourage a workshop atmosphere as much as possible.
All participants are invited to volunteer talks on recent work at the Informal
Talks Sessions. These will be scheduled at the conference.
Participants are also encouraged to bring preprints of recent papers.
The reception on Monday evening is hosted by the Mathematical Sciences
Institute of Cornell University.
Because of a generous donation made by the Mathematical Sciences Institute
a modest partial reimbursement of travel expenses to the conference may
be possible for full-time students who are not from the Cornell University
area and for attendees from outside the United States.
Full-time students and traveler's from abroad should bring a copy of their
flight coupon (or other verification of travel expenses) to the conference.
There will be an opportunity at that time to register for such reimbursement.
The conference is sponsored by the IEEE Computer Society's Technical
Committee on Mathematical Foundations of Computing, Cornell University,
and Northeastern University, and in cooperation with ACM-SIGACT.
Conference Chairman: Alan Selman.
Local Arrangements Chairman: Dexter Kozen.
Program Committee: Shafi Goldwasser, Juris Hartmanis,
Neil Immerman, Deborah Joseph, Stephen Mahaney (Chairman),
Uwe Schoning, Alan Selman, Mike Sipser, Larry Stockmeyer, and
Peter van Emde Boas.