| 1997 | A Lower Bound for Perceptrons and an Oracle Separation of the PP Christer Berg, Staffan Ulfberg |
| 1997 | A Nonadaptive NC Checker for Permutation Group Intersection. Vikraman Arvind, Jacobo Torán |
| 1997 | A Note on Universal Distributions for Polynomial-Time Computable Distributions. Rainer Schuler |
| 1997 | A Note on the Bottleneck Counting Argument. Janos Simon, Shi-Chun Tsai |
| 1997 | A Short Guide to Approximation Preserving Reductions. Pierluigi Crescenzi |
| 1997 | Acceptance by Transformation Monoids (with an Application to Local Self Reductions). Ulrich Hertrampf |
| 1997 | Circuit Bottom Fan-in and Computational Power. Liming Cai, Jianer Chen, Johan Håstad |
| 1997 | Circuits Over PP and PL. Richard Beigel, Bin Fu |
| 1997 | Circuits and Expressions with NOn-Associative Gates. Joshua Berman, Arthur Drisko, François Lemieux, Cristopher Moore, Denis Thérien |
| 1997 | Complexity and Expressive Power of Logic Programming. Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov |
| 1997 | Constraint Satisfaction: The Approximability of Minimization Problems. Sanjeev Khanna, Madhu Sudan, Luca Trevisan |
| 1997 | Finite Limits and Monotone Computations: The Lower Bounds Criterion. Stasys Jukna |
| 1997 | Hyper-Polynomial Hierarchies and the NP-Jump. Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer |
| 1997 | Inequalities for Shannon entropies and Kolmogorov complexities. Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
| 1997 | LR(k) Testing is Average Case Complete. Christoph Karg |
| 1997 | Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. Lance Fortnow |
| 1997 | On Operators of Higher Types. Heribert Vollmer, Klaus W. Wagner |
| 1997 | On Ranomization in Online Computation. Allan Borodin, Ran El-Yaniv |
| 1997 | On TC Manindra Agrawal, Eric Allender, Samir Datta |
| 1997 | Polynomial Vicinity Circuits and Nonlinear Lower Bounds. Kenneth W. Regan |
| 1997 | Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997 |
| 1997 | Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. László Babai, Peter G. Kimmel |
| 1997 | Reversible Space Equals Deterministic Space. Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp |
| 1997 | Separating NP-Completeness Notions under Strong Hypotheses. Klaus Ambos-Spies, Levke Bentzien |
| 1997 | Six Hypotheses in Search of a Theorem. Harry Buhrman, Lance Fortnow, Leen Torenvliet |
| 1997 | The Communication Complexity of the Universal Relation. Gábor Tardos, Uri Zwick |
| 1997 | The Density of Weakly Complete Problems under Adaptive Reductions. Jack H. Lutz, Yong Zhao |
| 1997 | The General Notion of a Dot-Operator. Bernd Borchert, Riccardo Silvestri |
| 1997 | Tight Bound on Johnson's Algoritihm for Max-SAT. Jianer Chen, Donald K. Friesen, Hao Zheng |
| 1997 | Time Bounded Frequency Computations. Maren Hinrichs, Gerd Wechsung |
| 1997 | Undecidability Results for Low Complexity Degree Structures. Rodney G. Downey, André Nies |
| 1997 | Upper and Lower Bounds for Some Depth-3 Circuit Classes. Richard Beigel, Alexis Maciel |