Computational Complexity, Volume 8

Volume 8, Number 1, 1999

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

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

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

Walter Baur, Karin Halupczok:
On lower bounds for the complexity of polynomials and their multiples. 309-315
Dima Grigoriev:
Complexity lower bounds for randomized computation trees over zero characteristic fields. 316-329
Sergei Ivanov, Michel de Rougemont:
Interactive protocols over the reals. 330-345
Hajime Ishihara:
Function algebraic characterizations of the polytime functions. 346-356
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
Martin Dietzfelbinger, Martin Hühne:
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape. 371-392