Volume 63, Number 1, August 2001
Volume 63, Number 2, September 2001
: Branching Program Size Is Almost Linear in Formula Size.
: Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.
: Integer Circuit Evaluation Is PSPACE-Complete.
Volume 63, Number 3, November 2001
: Tight Lower Bounds on the Size of Sweeping Automata.
Satyanarayana V. Lokam
: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity.
Volume 63, Number 4, December 2001