9. CoCo 1994: Amsterdam, The Netherlands

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

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 Sat May 25 02:32:54 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page