default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID8th SCT 1993: San Diego, California, USA
- Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993. IEEE Computer Society 1993, ISBN 0-8186-4070-7
Session 1
- Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao:
Towards Uncheatable benchmarks. 2-11 - Christos H. Papadimitriou, Mihalis Yannakakis:
On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract). 12-18 - Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi:
On Monadic NP vs. Monadic co-NP (Extended Abstract). 19-30 - Phokion G. Kolaitis, Madhukar N. Thakur:
Polynomial-time Optimization, Parallel Approximation, and Fixpoint Logic (Extended Abstract). 31-41
Session 2
- Harry Buhrman, Peter van Helden, Leen Torenvliet:
P-Selective Self-reducibles Sets: A New Characterization of P. 44-51 - Ashish V. Naik, Mitsunori Ogiwara, Alan L. Selman:
P-Selective Sets, and Reducing Search to Decision vs. Self-Reducability. 52-64 - Jay Belanger, Jie Wang:
Isomorphisms of NP Complete Problems on Random Instances. 65-74 - Manindra Agrawal, Somenath Biswas:
Polynomial Isomorphism of 1-L-Complete Sets. 75-80
Session 3
- Richard Beigel:
The Polynomial Method in Circuit Complexity. 82-95 - Shi-Chun Tsai:
Lower Bounds on Representing Boolean Functions as Polynomials in Zm. 96-101 - Mauricio Karchmer, Avi Wigderson:
On Span Programs. 102-111 - Mauricio Karchmer:
On Proving Lower Bounds for Circuit Size. 112-118
Session 4
- Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li:
An Oarcle Builder's Toolkit. 120-131 - Nikolai K. Vereshchagin:
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles. 132-138 - Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of #P in the Context of PF°#P. 139-146 - Johannes Köbler, Seinosuke Toda:
On the Power of Generalized MOD-Classes. 147-155
Session 5
- Jack H. Lutz:
The Quantitative Structure of Exponential Time. 158-175 - Suresh Chari, Pankaj Rohatgi:
On Completeness under Random Reductions. 176-184 - Bin Fu:
With Quasi-linear Queries, EXP is not Polynomial Time Turing Reducible to ?Sparse Sets. 185-191
Session 6
- Pierluigi Crescenzi, Riccardo Silvestri:
Sperner's Lemma and Robust Machines. 194-199 - Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner:
On the Power of Polynomial Time Bit-Reductions (Extended Abstract). 200-207 - Harry Buhrman, Luc Longpré, Edith Spaan:
SPARSE reduces conjunctively to TALLY. 208-214 - Sanjeev Saluja:
Relativized limitations of left set technique and closure classes of sparse sets (Extended Abstract). 215-222
Session 7
- Klaus-Jörn Lange:
Complexity and Structure in Formal Language Theory. 224-238 - Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo
:
Pointers versus Arithmetic in PRAMs. 239-252 - José L. Balcázar, Ricard Gavaldà, Hava T. Siegelmann, Eduardo D. Sontag:
Some Structural Complexity Aspects of Neural Computation. 253-265 - Sanjay Gupta:
Alternating Time Versus Deterministic Time: A Separation. 266-277
Session 8
- Birgit Jenner, Jacobo Torán:
Computing Functions with Parallel Queries to NP. 280-291 - Tirza Hirst, David Harel:
Taking it to the Limit: On Infinite Variants of NP-Complete Problems. 292-304 - David Zuckerman:
NP-Complete Problems Have a Version That's Hard to Approximate. 305-312 - Zhi-Zhong Chen, Seinosuke Toda:
The Complexity of Selecting Maximal Solutions. 313-325
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-04 22:07 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:
