8. CoCo 1993: San Diego, California, USA

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, May 18-21, 1993, San Diego, CA, USA. IEEE Computer Society Press, 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 Z_m. 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