Computational Complexity, Volume 8

Volume 8, Number 1, 1999

• Christer Berg, Staffan Ulfberg:
  Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers. 1-20
  Electronic Edition (Springer LINK) BibTeX
• Ilan Kremer, Noam Nisan, Dana Ron:
  On Randomized One-Round Communication Complexity. 21-49
  Electronic Edition (Springer LINK) BibTeX
• Oded Goldreich, Erez Petrank:
  Quantifying Knowledge Complexity. 50-98
  Electronic Edition (Springer LINK) BibTeX

Volume 8, Number 2, 1999

• Eric Allender, Robert Beals, Mitsunori Ogihara: The Complexity of Matrix Rank and Feasible Systems of Linear Equations. 99-126 BibTeX
• Russell Impagliazzo, Pavel Pudlák, Jiri Sgall: Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. 127-144 BibTeX
• Carlo Blundo, Alfredo De Santis, Giuseppe Persiano, Ugo Vaccaro: Randomness Complexity of Private Computation. 145-168 BibTeX
• Ashish V. Naik, Alan L. Selman: Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets. 169-187 BibTeX
• Bruce M. Kapron: Feasibly Continuous Type-Two Functionals. 188-201 BibTeX

Volume 8, Number 3, 1999

• Markus Bläser:
  Lower bounds for the multiplicative complexity of matrix multiplication. 203-226
  Electronic Edition (Springer LINK) BibTeX
• Ming-Deh A. Huang, Yiu-Chung Wong:
  Solvability of systems of polynomial congruences modulo a large prime. 227-257
  Electronic Edition (Springer LINK) BibTeX
• David A. Mix Barrington, Howard Straubing:
  Lower bounds for modular counting by circuits with modular gates. 258-272
  Electronic Edition (Springer LINK) BibTeX
• Maciej Liskiewicz, Rüdiger Reischuk:
  On small space complexity classes of stochastic Turing machines and Arthur-Merlin-games. 273-307
  Electronic Edition (Springer LINK) BibTeX

Volume 8, Number 4, 1999

• Walter Baur, Karin Halupczok:
  On lower bounds for the complexity of polynomials and their multiples. 309-315
  Electronic Edition (Springer LINK) BibTeX
• Dima Grigoriev:
  Complexity lower bounds for randomized computation trees over zero characteristic fields. 316-329
  Electronic Edition (Springer LINK) BibTeX
• Sergei Ivanov, Michel de Rougemont:
  Interactive protocols over the reals. 330-345
  Electronic Edition (Springer LINK) BibTeX
• Hajime Ishihara:
  Function algebraic characterizations of the polytime functions. 346-356
  Electronic Edition (Springer LINK) BibTeX
• Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener:
  On P versus NP cap co-NP for decision trees and read-once branching programs. 357-370
  Electronic Edition (Springer LINK) BibTeX
• Martin Dietzfelbinger, Martin Hühne:
  Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape. 371-392
  Electronic Edition (Springer LINK) BibTeX