Abstract is missing.
- Towards Uncheatable benchmarksJin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao. 2-11
- On Limited Nondeterminism and the Complexity of the V.C Dimension (Extended Abstract)Christos H. Papadimitriou, Mihalis Yannakakis. 12-18
- On Monadic NP vs. Monadic co-NP (Extended Abstract)Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi. 19-30
- Polynomial-time Optimization, Parallel Approximation, and Fixpoint Logic (Extended Abstract)Phokion G. Kolaitis, Madhukar N. Thakur. 31-41
- P-Selective Self-reducibles Sets: A New Characterization of ::::P::::Harry Buhrman, Peter van Helden, Leen Torenvliet. 44-51
- P-Selective Sets, and Reducing Search to Decision vs. Self-ReducabilityAshish V. Naik, Mitsunori Ogiwara, Alan L. Selman. 52-64
- Isomorphisms of NP Complete Problems on Random InstancesJay Belanger, Jie Wang. 65-74
- Polynomial Isomorphism of 1-L-Complete SetsManindra Agrawal, Somenath Biswas. 75-80
- The Polynomial Method in Circuit ComplexityRichard Beigel. 82-95
- Lower Bounds on Representing Boolean Functions as Polynomials in ::::Z::::::m::Shi-Chun Tsai. 96-101
- On Span ProgramsMauricio Karchmer, Avi Wigderson. 102-111
- On Proving Lower Bounds for Circuit SizeMauricio Karchmer. 112-118
- Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oraclesNikolai K. Vereshchagin. 132-138
- On Closure Properties of #P in the Context of PF°#PMitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe. 139-146
- On the Power of Generalized MOD-ClassesJohannes Köbler, Seinosuke Toda. 147-155
- The Quantitative Structure of Exponential TimeJack H. Lutz. 158-175
- On Completeness under Random ReductionsSuresh Chari, Pankaj Rohatgi. 176-184
- With Quasi-linear Queries, EXP is not Polynomial Time Turing Reducible to ?Sparse SetsBin Fu. 185-191
- Sperner s Lemma and Robust MachinesPierluigi Crescenzi, Riccardo Silvestri. 194-199
- On the Power of Polynomial Time Bit-Reductions (Extended Abstract)Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner. 200-207
- SPARSE reduces conjunctively to TALLYHarry Buhrman, Luc Longpré, Edith Spaan. 208-214
- Relativized limitations of left set technique and closure classes of sparse sets (Extended Abstract)Sanjeev Saluja. 215-222
- Complexity and Structure in Formal Language TheoryKlaus-Jörn Lange. 224-238
- Pointers versus Arithmetic in PRAMsPatrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo. 239-252
- Some Structural Complexity Aspects of Neural ComputationJosé L. Balcázar, Ricard Gavaldà, Hava T. Siegelmann, Eduardo D. Sontag. 253-265
- Computing Functions with Parallel Queries to NPBirgit Jenner, Jacobo Torán. 280-291
- Taking it to the Limit: On Infinite Variants of NP-Complete ProblemsTirza Hirst, David Harel. 292-304
- NP-Complete Problems Have a Version That s Hard to ApproximateDavid Zuckerman. 305-312
- The Complexity of Selecting Maximal SolutionsZhi-Zhong Chen, Seinosuke Toda. 313-325