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
  

Last update Sat May 25 15:35:50 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page