Computational Complexity, Volume 9

Volume 9, Number 1, 2000

• Ramamohan Paturi, Michael E. Saks, Francis Zane:
  Exponential lower bounds for depth three Boolean circuits. 1-15
  
• Frederic Green:
  A complex-number Fourier technique for lower bounds on the Mod-m degree. 16-38
  
• Anna Bernasconi, Carsten Damm, Igor Shparlinski:
  The average sensitivity of square-freeness. 39-51
  
• Catherine S. Greenhill:
  The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. 52-72
  

Volume 9, Number 2, 2000

• Markus Bläser:
  Lower bounds for the bilinear complexity of associative algebras. 73-112
  
• Ran Raz:
  The BNS-Chung criterion for multi-party communication complexity. 113-122
  
• Carme Àlvarez, Raymond Greenlaw:
  A compendium of problems complete for symmetric logarithmic space. 123-145
  
• F. Blume:
  On the relation between entropy and the average complexity of trajectories in dynamical systems. 146-155
  

Volume 9, Number 3-4, 2000

• Prahladh Harsha, Madhu Sudan:
  Small PCPs with low query complexity. 157-201
  
• Marcos A. Kiwi, Carsten Lund, Daniel A. Spielman, Alexander Russell, Ravi Sundaram:
  Alternation in interaction. 202-246
  
• Detlef Sieling:
  A separation of syntactic and nonsyntactic (1, +k)-branching programs. 247-263