| 2001 | A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. Jürgen Forster |
| 2001 | A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. Jack Jie Dai |
| 2001 | Affine Projections of Symmetric Polynomials. Amir Shpilka |
| 2001 | Bounded Query Functions with Limited Output Bits. Richard Chang, Jon S. Squire |
| 2001 | Communication Complexity Lower Bounds by Polynomials. Harry Buhrman, Ronald de Wolf |
| 2001 | Comparing Notions of Full Derandomization. Lance Fortnow |
| 2001 | Computational Depth. Luis Antunes, Lance Fortnow, Dieter van Melkebeek |
| 2001 | Hausdorff Dimension in Exponential Time. Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan |
| 2001 | In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
| 2001 | Links Between Complexity Theory and Constrained Block Coding. Larry J. Stockmeyer, Dharmendra S. Modha |
| 2001 | Logical Operations and Kolmogorov Complexity II. Andrei A. Muchnik, Nikolai K. Vereshchagin |
| 2001 | Lower Bounds for Approximations by Low Degree Polynomials Over Z Noga Alon, Richard Beigel |
| 2001 | Monotone Simulations of Nonmonotone Proofs. Albert Atserias, Nicola Galesi, Pavel Pudlák |
| 2001 | On Separators, Segregators and Time versus Space. Rahul Santhanam |
| 2001 | On the Complexity of Approximating the VC Dimension. Elchanan Mossel, Christopher Umans |
| 2001 | On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. Beate Bollig, Martin Sauerhoff, Ingo Wegener |
| 2001 | On the Power of Nonlinear Secrect-Sharing. Amos Beimel, Yuval Ishai |
| 2001 | Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001 |
| 2001 | Quantum Algorithmic Entropy. Péter Gács |
| 2001 | Quantum Algorithms for Element Distinctness. Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf |
| 2001 | Quantum versus Classical Learnability. Rocco A. Servedio, Steven J. Gortler |
| 2001 | Resolution Complexity of Independent Sets in Random Graphs. Paul Beame, Russell Impagliazzo, Ashish Sabharwal |
| 2001 | Separation of NP-Completeness Notions. Aduri Pavan, Alan L. Selman |
| 2001 | Simple Analysis of Graph Tests for Linearity and PCP. Johan Håstad, Avi Wigderson |
| 2001 | Space Complexity of Random Formulae in Resolution. Eli Ben-Sasson, Nicola Galesi |
| 2001 | Time-Space Tradeoffs in the Counting Hierarchy. Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
| 2001 | Towards Proving Strong Direct Product Theorems. Ronen Shaltiel |
| 2001 | Towards Uniform AC Manindra Agrawal |
| 2001 | Tree Resolution Proofs of the Weak Pigeon-Hole Principle. Stefan S. Dantchev, Søren Riis |
| 2001 | Uniform Circuits for Division: Consequences and Problems. Eric Allender, David A. Mix Barrington, William Hesse |
| 2001 | Universal Traversal Sequences with Backtracking. Michal Koucký |