12. CoCo 1997: Ulm, Germany

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, June 24-27, 1997, Ulm, Germany. IEEE Computer Society Press, 1997, ISBN 0-8186-7907-7

Session 1

Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Six Hypotheses in Search of a Theorem. 2-12
Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Inequalities for Shannon entropies and Kolmogorov complexities. 13-23
Richard Beigel, Bin Fu:
Circuits Over PP and PL. 24-35
Bernd Borchert, Riccardo Silvestri:
The General Notion of a Dot-Operator. 36-44
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp:
Reversible Space Equals Deterministic Space. 45-50

Session 2

Lance Fortnow:
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. 52-60
Kenneth W. Regan:
Polynomial Vicinity Circuits and Nonlinear Lower Bounds. 61-68
Rainer Schuler:
A Note on Universal Distributions for Polynomial-Time Computable Distributions. 69-73
Christoph Karg:
LR(k) Testing is Average Case Complete. 74-80

Session 3

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov:
Complexity and Expressive Power of Logic Programming. 82-101
Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer:
Hyper-Polynomial Hierarchies and the NP-Jump. 102-110
Jack H. Lutz, Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions. 111-120
Klaus Ambos-Spies, Levke Bentzien:
Separating NP-Completeness Notions under Strong Hypotheses. 121-127
Rodney G. Downey, André Nies:
Undecidability Results for Low Complexity Degree Structures. 128-132

Session 4

Manindra Agrawal, Eric Allender, Samir Datta:
On TC⁰, AC⁰, and Arithmetic Circuits. 134-148
Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. 149-157
Liming Cai, Jianer Chen, Johan Håstad:
Circuit Bottom Fan-in and Computational Power. 158-164
Christer Berg, Staffan Ulfberg:
A Lower Bound for Perceptrons and an Oracle Separation of the PP^PH Hierarchy. 165-172

Session 5

Heribert Vollmer, Klaus W. Wagner:
On Operators of Higher Types. 174-184
Maren Hinrichs, Gerd Wechsung:
Time Bounded Frequency Computations. 185-192
Joshua Berman, Arthur Drisko, François Lemieux, Cristopher Moore, Denis Thérien:
Circuits and Expressions with NOn-Associative Gates. 193-203
Vikraman Arvind, Jacobo Torán:
A Nonadaptive NC Checker for Permutation Group Intersection. 204-212
Ulrich Hertrampf:
Acceptance by Transformation Monoids (with an Application to Local Self Reductions). 213-224

Session 6

Allan Borodin, Ran El-Yaniv:
On Ranomization in Online Computation. 226-238
László Babai, Peter G. Kimmel:
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. 239-246
Gábor Tardos, Uri Zwick:
The Communication Complexity of the Universal Relation. 247-259

Session 7

Pierluigi Crescenzi:
A Short Guide to Approximation Preserving Reductions. 262-273
Jianer Chen, Donald K. Friesen, Hao Zheng:
Tight Bound on Johnson's Algoritihm for Max-SAT. 274-281
Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint Satisfaction: The Approximability of Minimization Problems. 282-296
Janos Simon, Shi-Chun Tsai:
A Note on the Bottleneck Counting Argument. 297-301
Stasys Jukna:
Finite Limits and Monotone Computations: The Lower Bounds Criterion. 302-313