default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID16th CCC 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
- 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 Zm. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-13 20:20 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
