| 1996 | A Comparison of Weak Completeness Notions. Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng |
| 1996 | A Note on Decision versus Search for Graph Automorphism. Manindra Agrawal, Vikraman Arvind |
| 1996 | A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. Ashish V. Naik, Alan L. Selman |
| 1996 | An Isomorphism Theorem for Circuit Complexity. Manindra Agrawal, Eric Allender |
| 1996 | Collapsing Oracle-Tape Hierarchies. Georg Gottlob |
| 1996 | Complements of Multivalued Functions. Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer |
| 1996 | DNA Models and Algorithms for NP-complete Problems. Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay |
| 1996 | Deciding the Vapnik-Cervonenkis dimension is Sigma Marcus Schäfer |
| 1996 | Error Reduction by Parallel Repetition - a Negative Result. Uriel Feige, Oleg Verbitsky |
| 1996 | Extracting Randomness: How and Why A survey. Noam Nisan |
| 1996 | Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. Samuel R. Buss, Toniann Pitassi |
| 1996 | Hierarchies of Circuit Classes that are Closed under Complement. V. Vinay |
| 1996 | Integer Programming as a Framework for Optimization and Approximability. Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur |
| 1996 | Inverting Onto Functions. Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers |
| 1996 | L-Printable Sets. Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney |
| 1996 | Much Ado about Functions. Alan L. Selman |
| 1996 | Nondeterministic NC Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer |
| 1996 | On Coherence, Random-self-reducibility, and Self-correction. Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik |
| 1996 | On Positive P. Clemens Lautemann, Thomas Schwentick, Iain A. Stewart |
| 1996 | On the Measure of Two-Dimensional Regions with Polynomial-Time computables Boundaries. Ker-I Ko, Klaus Weihrauch |
| 1996 | Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits. Kazuo Iwama, Chuzo Iwamoto |
| 1996 | Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996 Steven Homer, Jin-Yi Cai |
| 1996 | Randomization and Derandomization in Space_Bounded Computation. Michael E. Saks |
| 1996 | Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. Dieter van Melkebeek |
| 1996 | Reversible Simulation of Irreversible Computation. Ming Li, Paul M. B. Vitányi |
| 1996 | Succinct Representation, Leaf Languages, and Projection Reductions. Helmut Veith |
| 1996 | The Complexity of Knowledge Representation. Christos H. Papadimitriou |
| 1996 | The Law of the Iterated Logarithm for p-Random Sequences. Yongge Wang |
| 1996 | Truth-table Closure and Turing Closure of Average Polynomial Time have Different Measures in EXP. Rainer Schuler |
| 1996 | VC Dimension in Circuit Complexity. Pascal Koiran |
| 1996 | Zero Knowledge and the Chromatic Number. Uriel Feige, Joe Kilian |