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
Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. 14-19
Thomas Hofmeister: The Power of Negative Thinking in Constructing Threshold Circuits for Addition. 20-26
Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. 27-33

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 8

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

Last update Tue Feb 14 03:51:38 2012 CET by the DBLP Team —

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