Proceedings ... Annnual IEEE Conference on Computational Complexity, Volume 16, Part 2001

Front Cover
IEEE Computer Society Press - Computational complexity
0 Reviews

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Towards Uniform AC0lsomorphisms
19
Session 2
35
Resolution Complexity of Independent Sets in Random Graphs
52
Tree Resolution Proofs of the Weak PigeonHole Principle
69
Bounded Query Functions with Limited Output Bits
90
Session 4
99
Towards Proving Strong Direct Product Theorems
107
Session 5
119
On the NonApproximability of Boolean Functions by OBDDs
172
Lower Bounds for Approximations by Low Degree Polynomials Over Zm
184
A Stronger Kolmogorov ZeroOne Law for ResourceBounded Measure
204
Hausdorff Dimension in Exponential Time
210
Session 8
219
Links Between Complexity Theory and Constrained Block Coding
226
Simple Analysis of Graph Tests for Linearity and PCP
244
Session 9
255

Quantum Algorithms for Element Distinctness
131
Quantum versus Classical Leamability
138
Session 6
149
Affine Projections of Symmetric Polynomials
160
Quantum Algorithmic Entropy
274
TimeSpace Tradeoffs in the Counting Hierarchy
295
Copyright

Bibliographic information