16. CoCo 2001: Chicago, Illinois, USA

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 18-21 June 2001, Chicago, Illinois, USA. IEEE Computer Society, 2001, ISBN 0-7695-1053-1

Session 1

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

Session 2

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

Session 3

Aduri Pavan, Alan L. Selman:
Separation of NP-Completeness Notions. 78-89
Electronic Edition (IEEE Computer Society DL) BibTeX
Richard Chang, Jon S. Squire:
Bounded Query Functions with Limited Output Bits. 90-98
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4

Jürgen Forster:
A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. 100-106
Electronic Edition (IEEE Computer Society DL) BibTeX
Ronen Shaltiel:
Towards Proving Strong Direct Product Theorems. 107-117
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5

Harry Buhrman, Ronald de Wolf:
Communication Complexity Lower Bounds by Polynomials. 120-130
Electronic Edition (IEEE Computer Society DL) BibTeX
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
Electronic Edition (IEEE Computer Society DL) BibTeX
Rocco A. Servedio, Steven J. Gortler:
Quantum versus Classical Learnability. 138-148
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6

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

Session 7

Jack Jie Dai:
A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. 204-209
Electronic Edition (IEEE Computer Society DL) BibTeX
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan:
Hausdorff Dimension in Exponential Time. 210-217
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8

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

Session 9

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

Session 10

Rahul Santhanam:
On Separators, Segregators and Time versus Space. 286-294
Electronic Edition (IEEE Computer Society DL) BibTeX
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
Time-Space Tradeoffs in the Counting Hierarchy. 295-302
Electronic Edition (IEEE Computer Society DL) BibTeX