Computational Complexity, Volume 7

Volume 7, Number 1, 1998

• Vince Grolmusz: Circuits and Multi-Party Protocols. 1-18
• Howard Aizenstein, Tibor Hegedüs, Lisa Hellerstein, Leonard Pitt: Complexity Theoretic Hardness Results for Query Learning. 19-53
• Etienne Grandjean, Frédéric Olive: Monadic Logical Definability of Nondeterministic Linear Time. 54-97

Volume 7, Number 2, 1998

• Gábor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree of the Or Function. 99-108
• Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping. 109-127
• Miklos Santha, Sovanna Tan: Verifying the Determinant in Parallel. 128-151
• Alexander Russell, Ravi Sundaram: Symmetric Alternation Captures BPP. 152-162
• Pierluigi Crescenzi, Riccardo Silvestri: Sperner's Lemma and Robust Machines. 163-173
• Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik: On Coherence, Random-Self-Reducibility, and Self-Correction. 174-191

Volume 7, Number 3, 1998

• Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao:
  An exponential lower bound on the size of algebraic decision trees for Max. 193-203
  
• Lavinia Egidi:
  A quantifier elimination for the theory of p-adic numbers. 205-263
  
• Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
  Probabilistic Type-2 Operators and "Almost"-Classes. 265-289
  

Volume 7, Number 4, 1998

• Alexander A. Razborov:
  Lower Bounds for the Polynomial Calculus. 291-324
  
• Paul Beame, Russell Impagliazzo, Toniann Pitassi:
  Improved Depth Lower Bounds for Small Distance Connectivity. 325-345
  
• Matthias Krause, Pavel Pudlák:
  Computing Boolean Functions by Polynomials and Threshold Circuits. 346-370
  
• Ian Glaister, Jeffrey Shallit:
  Automaticity III: Polynomial Automaticity and Context-Free Languages. 371-387