9. CoCo 1994: Amsterdam, The Netherlands

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, June 28 - July 1, 1994, Amsterdam, The Netherlands. IEEE Computer Society Press, 1994, ISBN 0-8186-5670-0

Session 1

Mitsunori Ogihara: Polynomial-Time Membership Comparable Sets. 2-11 BibTeX
Richard Beigel, Martin Kummer, Frank Stephan: Approximable Sets. 12-23 BibTeX
Manindra Agrawal, Vikraman Arvind: Polynomial Time Truth-Table Reductions to P-Selective Sets. 24-30 BibTeX
Richard Chang: On the Query Complexity of Clique Size and Maximum Satisfiability. 31-42 BibTeX
Harry Buhrman, Jim Kadin, Thomas Thierauf: On Functions Computable with Nonadaptive Queries to NP. 43-52 BibTeX
Sarah Mocas: Using Bounded Query Classes to Separate Classes in the Exponential Time Hierarchy from Classes in PH. 53-58 BibTeX
Avi Wigderson: NL/poly <= +/poly (Preliminary Version). 59-62 BibTeX

Session 2

Maciej Liskiewicz, Rüdiger Reischuk: The Complexity World below Logarithmic Space. 64-78 BibTeX
Richard J. Lipton: Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions. 79-87 BibTeX
Russell Impagliazzo, Ran Raz, Avi Wigderson: A Direct Product Theorem. 88-96 BibTeX
Shai Ben-David, Mauricio Karchmer, Eyal Kushilevitz: On Ultrafilters and NP. 97-105 BibTeX
Klaus-Jörn Lange, Peter Rossmanith: Unambiguous Polynomial Hierarchies and Exponential Size. 106-115 BibTeX

Session 3

Harry Buhrman, Leen Torenvliet: On the Structure of Complete Sets. 118-133 BibTeX
Richard Beigel, Judy Goldsmith: Downward separation fails catastrophically for limited nondeterminism classes. 134-138 BibTeX
Lance Fortnow, Tomoyuki Yamakami: Generic Separations. 139-145 BibTeX
Jack H. Lutz: Weakly Hard Problems. 146-161 BibTeX
Steven M. Kautz, Peter Bro Miltersen: Relative to a Random Oracle, NP is Not Small. 162-174 BibTeX

Session 4

David A. Mix Barrington, Neil Immerman: Time, Hardware, and Uniformity. 176-185 BibTeX
Xiangdong Yu, Moti Yung: Space Lower-Bounds for Pseudorandom-Generators. 186-197 BibTeX
Bernd Meyer: Constructive Separation of Classes of Indistinguishable Ensembles. 198-204 BibTeX
Osamu Watanabe: Test Instance Generation for Promise NP Search Problems. 205-216 BibTeX
Harry Buhrman, Pekka Orponen: Random Strings Make Hard Instances. 217-222 BibTeX

Session 5

Ulrich Hertrampf: Complexity Classes Defined via k-valued Functions. 224-234 BibTeX
Bernd Borchert: Predicate Classes and Promise Classes. 235-241 BibTeX
Birgit Jenner, Pierre McKenzie, Denis Thérien: Logspace and Logtime Leaf Languages. 242-254 BibTeX
Kevin J. Compton, Erich Grädel: Logical Definability of Counting Functions. 255-266 BibTeX
Eric Allender, Mitsunori Ogihara: Relationships Among PL, #L, and the Determinant. 267-278 BibTeX

Session 6

Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor: Random Debaters and the Hardness of Approximating Stochastic Functions. 280-293 BibTeX
Marcos A. Kiwi, Carsten Lund, Alexander Russell, Daniel A. Spielman, Ravi Sundaram: Alternation in Interaction. 294-303 BibTeX
Oleg Verbitsky: Towards the Parallel Repetition Conjecture. 304-307 BibTeX
Gábor Tardos: Multi-Prover Encoding Schemes and Three-Prover Proof Systems. 308-317 BibTeX
Christos H. Papadimitriou, John N. Tsitsiklis: The Complexity of Optimal Queueing Network Control. 318-322 BibTeX

Session 7

Ricard Gavaldà: The Complexity of Learning with Queries. 324-337 BibTeX
Manindra Agrawal: On the Isomorphism Problem for Weak Reducibilities. 338-355 BibTeX
Harry B. Hunt III, Madhav V. Marathe, Richard Edwin Stearns: Generalized CNF Satisfiability Problems and Non-Efficient. 356-366 BibTeX
Deborah Joseph, Randall Pruim, Paul Young: Collapsing Degrees in Subexponential Time. 367-382 BibTeX
Pavel Pudlák: Complexity Theory and Genetics. 383-395 BibTeX