7. CoCo 1992: Boston, Massachusetts, USA

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, June 22-25, 1992, Boston, Massachusetts, USA. IEEE Computer Society Press, 1992, ISBN 0-8186-2955-X

Session 1

Mikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates vs. General Weighted Threshold Gates. 2-13 BibTeX
Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. 14-19 BibTeX
Thomas Hofmeister: The Power of Negative Thinking in Constructing Threshold Circuits for Addition. 20-26 BibTeX
Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. 27-33 BibTeX

Session 2

Rodney G. Downey, Michael R. Fellows: Fixed-Parameter Intractability. 36-49 BibTeX
Bin Fu, Hong-Zhou Li, Yong Zhong: Some Properties of Exponential Time Complexity Classes. 50-57 BibTeX
J. Ramachandran: Set Bit Enumeration is Hard. 58-70 BibTeX
Pankaj Rohatgi: Saving Queries with Randomness. 71-83 BibTeX

Session 3

David A. Mix Barrington: Quasipolynomial Size Circuit Classes. 86-93 BibTeX
Martin Beaudry, Pierre McKenzie: Cicuits, Matrices, and Nonassociative Computation. 94-106 BibTeX
Michael R. Fellows, Neal Koblitz: Self-Witnessing Polynomial-Time Complexity and Prime Factorization. 107-110 BibTeX
Frederic Green, Johannes Köbler, Jacobo Torán: The Power of the Middle Bit. 111-117 BibTeX
Antoni Lozano, Jacobo Torán: On the Nonuniform Complexity on the Graph Isomorphism Problem. 118-129 BibTeX

Session 4

André Berthiaume, Gilles Brassard: The Quantum Challenge to Structural Complexity Theory. 132-137 BibTeX
Nikolai K. Vereshchagin: On The Power of PP. 138-143 BibTeX
Lide Li: Formal Power Series: An Algebraic Approach to the GapP and #P Functions. 144-154 BibTeX

Session 5

Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Fixpoint Logics, Relational Machines, and Computational Complexity. 156-168 BibTeX
Sanjeev Saluja, K. V. Subrahmanyam, Madhukar N. Thakur: Descriptive Complexity of #P Functions. 169-184 BibTeX
Steven Lindell: A Purely Logical Characterization of Circuit Uniformity. 185-192 BibTeX
Stephen A. Bloch: Functional Characterizations of Uniform Log-depth and Polylog-depth Circuit Families. 193-206 BibTeX
Manindra Agrawal, Somenath Biswas: Universal Relations. 207-220 BibTeX

Session 6

Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: How Hard Are Sparse Sets? 222-238 BibTeX
Desh Ranjan, Pankaj Rohatgi: On Randomized Reductions to Sparse Sets. 239-242 BibTeX
Bin Fu, Hong-Zhou Li: On Closeness of NP-Hard Sets to Other Complexity Classes. 243-248 BibTeX
Ricard Gavaldà: Bounding the Complexity of Advice Functions. 249-254 BibTeX
Ronald V. Book, Jack H. Lutz: On Languages with Very High Information Content. 255-259 BibTeX

Session 7

Mauricio Karchmer, Eyal Kushilevitz, Noam Nisan: Fractional Covers and Communication Complexity. 262-274 BibTeX
Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-deterministic Communication Complexity with Few Witness. 275-281 BibTeX
Anne Condon, Richard E. Ladner: Interactive Proof Systems with Polynomially Bounded Strategies. 282-294 BibTeX
Farrokh Vatan: Some Lower and Upper Bounds for Algebraic Decision Trees and the Separation Problem. 295-304 BibTeX

Session 8

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer: Average Dependence and Random Oracles. 306-317 BibTeX
Jie Wang, Jay Belanger: On Average P vs. Average NP. 318-326 BibTeX
Ker-I Ko: A Note on the Instance Complexity of Pseudorandom Sets. 327-337 BibTeX
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman: The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. 338-346 BibTeX