default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID7th SCT 1992: Boston, Massachusetts, USA
- Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992. IEEE Computer Society 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-08 09:49 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
