Computational Complexity, Volume 12

Volume 12, Numbers 1-2, June 2003

• Ronen Shaltiel:
  Towards proving strong direct product theorems. 1-22
  
• Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor Shparlinski:
  Complexity of some arithmetic problems for binary polynomials. 23-47
  
• John Watrous:
  On the complexity of simulating space-bounded quantum computations. 48-84
  

Volume 12, Numbers 3-4, December 2003

• Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma:
  Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. 85-130
  
• Andreas Bley:
  On the complexity of vertex-disjoint length-restricted path problems. 131-149
  
• Qi Cheng:
  Straight-line programs and torsion points on elliptic curves. 150-161
  
• Takashi Mihara, Shao Chin Sung:
  Deterministic polynomial-time quantum algorithms for Simon's problem. 162-175