16. CoCo 2001: Chicago, Illinois, USA

Session 1

• Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
  In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. 2-12
  
• Manindra Agrawal:
  Towards Uniform AC⁰ - Isomorphisms. 13-20
  
• Michal Koucký:
  Universal Traversal Sequences with Backtracking. 21-27
  
• Lance Fortnow:
  Comparing Notions of Full Derandomization. 28-34
  

Session 2

• Albert Atserias, Nicola Galesi, Pavel Pudlák:
  Monotone Simulations of Nonmonotone Proofs. 36-41
  
• Eli Ben-Sasson, Nicola Galesi:
  Space Complexity of Random Formulae in Resolution. 42-51
  
• Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
  Resolution Complexity of Independent Sets in Random Graphs. 52-68
  
• Stefan S. Dantchev, Søren Riis:
  Tree Resolution Proofs of the Weak Pigeon-Hole Principle. 69-75
  

Session 3

• Aduri Pavan, Alan L. Selman:
  Separation of NP-Completeness Notions. 78-89
  
• Richard Chang, Jon S. Squire:
  Bounded Query Functions with Limited Output Bits. 90-98
  

Session 4

• Jürgen Forster:
  A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. 100-106
  
• Ronen Shaltiel:
  Towards Proving Strong Direct Product Theorems. 107-117
  

Session 5

• Harry Buhrman, Ronald de Wolf:
  Communication Complexity Lower Bounds by Polynomials. 120-130
  
• Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf:
  Quantum Algorithms for Element Distinctness. 131-137
  
• Rocco A. Servedio, Steven J. Gortler:
  Quantum versus Classical Learnability. 138-148
  

Session 6

• Eric Allender, David A. Mix Barrington, William Hesse:
  Uniform Circuits for Division: Consequences and Problems. 150-159
  
• Amir Shpilka:
  Affine Projections of Symmetric Polynomials. 160-171
  
• Beate Bollig, Martin Sauerhoff, Ingo Wegener:
  On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. 172-183
  
• Noga Alon, Richard Beigel:
  Lower Bounds for Approximations by Low Degree Polynomials Over Z_m. 184-187
  
• Amos Beimel, Yuval Ishai:
  On the Power of Nonlinear Secrect-Sharing. 188-202
  

Session 7

• Jack Jie Dai:
  A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. 204-209
  
• Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan:
  Hausdorff Dimension in Exponential Time. 210-217
  

Session 8

• Elchanan Mossel, Christopher Umans:
  On the Complexity of Approximating the VC Dimension. 220-225
  
• Larry J. Stockmeyer, Dharmendra S. Modha:
  Links Between Complexity Theory and Constrained Block Coding. 226-243
  
• Johan Håstad, Avi Wigderson:
  Simple Analysis of Graph Tests for Linearity and PCP. 244-254
  

Session 9

• Andrei A. Muchnik, Nikolai K. Vereshchagin:
  Logical Operations and Kolmogorov Complexity II. 256-265
  
• Luis Antunes, Lance Fortnow, Dieter van Melkebeek:
  Computational Depth. 266-273
  
• Péter Gács:
  Quantum Algorithmic Entropy. 274-283
  

Session 10

• Rahul Santhanam:
  On Separators, Segregators and Time versus Space. 286-294
  
• Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
  Time-Space Tradeoffs in the Counting Hierarchy. 295-302