- 2001
- Manindra Agrawal:
Towards Uniform AC0 - Isomorphisms. CCC 2001: 13-20 - Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. CCC 2001: 150-159 - Eric Allender, Michal Koucký
, Detlef Ronneburger, Sambuddha Roy, V. Vinay:
Time-Space Tradeoffs in the Counting Hierarchy. CCC 2001: 295-302 - Noga Alon, Richard Beigel:
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. CCC 2001: 184-187 - Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan:
Hausdorff Dimension in Exponential Time. CCC 2001: 210-217 - Luis Antunes, Lance Fortnow, Dieter van Melkebeek:
Computational Depth. CCC 2001: 266-273 - Albert Atserias, Nicola Galesi, Pavel Pudlák:
Monotone Simulations of Nonmonotone Proofs. CCC 2001: 36-41 - Paul Beame
, Russell Impagliazzo
, Ashish Sabharwal:
Resolution Complexity of Independent Sets in Random Graphs. CCC 2001: 52-68 - Amos Beimel, Yuval Ishai:
On the Power of Nonlinear Secrect-Sharing. CCC 2001: 188-202 - Eli Ben-Sasson, Nicola Galesi:
Space Complexity of Random Formulae in Resolution. CCC 2001: 42-51 - Beate Bollig, Martin Sauerhoff, Ingo Wegener:
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. CCC 2001: 172-183 - Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer
, Frédéric Magniez, Miklos Santha, Ronald de Wolf:
Quantum Algorithms for Element Distinctness. CCC 2001: 131-137 - Harry Buhrman, Ronald de Wolf:
Communication Complexity Lower Bounds by Polynomials. CCC 2001: 120-130 - Richard Chang, Jon S. Squire:
Bounded Query Functions with Limited Output Bits. CCC 2001: 90-98 - Jack Jie Dai:
A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. CCC 2001: 204-209 - Stefan S. Dantchev, Søren Riis
:
Tree Resolution Proofs of the Weak Pigeon-Hole Principle. CCC 2001: 69-75 - Jürgen Forster:
A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. CCC 2001: 100-106 - Lance Fortnow:
Comparing Notions of Full Derandomization. CCC 2001: 28-34 - Péter Gács:
Quantum Algorithmic Entropy. CCC 2001: 274-283 - Johan Håstad, Avi Wigderson:
Simple Analysis of Graph Tests for Linearity and PCP. CCC 2001: 244-254 - Russell Impagliazzo
, Valentine Kabanets, Avi Wigderson:
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. CCC 2001: 2-12 - Michal Koucký:
Universal Traversal Sequences with Backtracking. CCC 2001: 21-27 - Elchanan Mossel, Christopher Umans:
On the Complexity of Approximating the VC Dimension. CCC 2001: 220-225 - Andrei A. Muchnik, Nikolai K. Vereshchagin
:
Logical Operations and Kolmogorov Complexity II. CCC 2001: 256-265 - Aduri Pavan, Alan L. Selman:
Separation of NP-Completeness Notions. CCC 2001: 78-89 - Rahul Santhanam:
On Separators, Segregators and Time versus Space. CCC 2001: 286-294 - Rocco A. Servedio, Steven J. Gortler:
Quantum versus Classical Learnability. CCC 2001: 138-148 - Ronen Shaltiel:
Towards Proving Strong Direct Product Theorems. CCC 2001: 107-117 - Amir Shpilka
:
Affine Projections of Symmetric Polynomials. CCC 2001: 160-171 - Larry J. Stockmeyer, Dharmendra S. Modha:
Links Between Complexity Theory and Constrained Block Coding. CCC 2001: 226-243