9. CoCo 1994: Amsterdam, The Netherlands

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Last update Mon Feb 13 04:21:50 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page