Computational Complexity, Volume 10

Volume 10, Number 1, 2001

• Amir Shpilka, Avi Wigderson:
  Depth-3 arithmetic circuits over fields of characteristic zero. 1-27
  Electronic Edition (Springer LINK) BibTeX
• Hana Chockler, Uri Zwick:
  Which bases admit non-trivial shrinkage of formulae? 28-40
  Electronic Edition (Springer LINK) BibTeX
• Mark Giesbrecht:
  Fast computation of the Smith form of a sparse integer matrix. 41-69
  Electronic Edition (Springer LINK) BibTeX
• Christoph Meinel, Stephan Waack:
  The "log rank" conjecture for modular communication complexity. 70-91
  Electronic Edition (Springer LINK) BibTeX

Volume 10, Number 2, 2001

• Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet:
  Two oracles that force a big crunch. 93-116
  Electronic Edition (Springer LINK) BibTeX
• Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
  Reducing the complexity of reductions. 117-138
  Electronic Edition (Springer LINK) BibTeX
• Dima Grigoriev:
  Complexity of Positivstellensatz proofs for the knapsack. 139-154
  Electronic Edition (Springer LINK) BibTeX
• Martin Sauerhoff:
  On the size of randomized OBDDs and read-once branching programs for k-stable functions. 155-178
  Electronic Edition (Springer LINK) BibTeX

Volume 10, Number 3, 2001

• Søren Riis:
  A complexity gap for tree resolution. 179-209
  Electronic Edition (Springer LINK) BibTeX
• Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall:
  Communication complexity towards lower bounds on circuit depth. 210-246
  Electronic Edition (Springer LINK) BibTeX
• Chi-Jen Lu:
  Derandomizing Arthur-Merlin games under uniform assumptions. 247-259
  Electronic Edition (Springer LINK) BibTeX

Volume 10, Number 4, December 2001

• Maria Luisa Bonet, Nicola Galesi:
  Optimality of size-width tradeoffs for resolution. 261-276
  Electronic Edition (link) BibTeX
• Anna Gál:
  A characterization of span program size and improved lower bounds for monotone span programs. 277-296
  Electronic Edition (link) BibTeX
• Matthias Krause, Stefan Lucks:
  Pseudorandom functions in TC⁰ and cryptographic limitations to proving lower bounds. 297-313
  Electronic Edition (link) BibTeX
• Ilan Kremer, Noam Nisan, Dana Ron:
  Errata for: "On randomized one-round communication complexity". 314-315
  Electronic Edition (link) BibTeX