default search action
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
Volume 8, Number 2, 1999
- Eric Allender, Robert Beals, Mitsunori Ogihara:
The Complexity of Matrix Rank and Feasible Systems of Linear Equations. 99-126 - Russell Impagliazzo
, Pavel Pudlák, Jirí Sgall
Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. 127-144 - Carlo Blundo, Alfredo De Santis
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
Volume 8, Number 3, 1999
- 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
Volume 8, Number 4, 1999
- 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
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
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape. 371-392
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-13 19:10 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: