16. CoCo 2001: Chicago, Illinois, USA
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001. 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
- Manindra Agrawal: Towards Uniform AC0 - Isomorphisms. 13-20
- Michal Koucký: Universal Traversal Sequences with Backtracking. 21-27
- Lance Fortnow: Comparing Notions of Full Derandomization. 28-34
Session 2
- Paul Beame, Russell Impagliazzo, Ashish Sabharwal: Resolution Complexity of Independent Sets in Random Graphs. 52-68
Session 3
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, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. 131-137
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 Zm. 184-187
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
- Larry J. Stockmeyer, Dharmendra S. Modha: Links Between Complexity Theory and Constrained Block Coding. 226-243
Session 9
- Andrei A. Muchnik, Nikolai K. Vereshchagin: Logical Operations and Kolmogorov Complexity II. 256-265
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team