Journal of Complexity, Volume 15

Volume 15, Number 1, March 1999

• David Eppstein, Giuseppe F. Italiano:
  PREFACE: Festschrift for Zvi Galil. 1-3
  
• Alberto Apostolico, Gad M. Landau, Steven Skiena:
  Matching for Run-Length Encoded Strings. 4-16
  
• Don Coppersmith, Baruch Schieber:
  Lower Bounds on the Depth of Monotone Arithmetic Computations. 17-29
  
• Raffaele Giancarlo, Roberto Grossi:
  Parallel Construction and Query of Index Data Structures for Pattern Matching on Square Matrices. 30-71
  
• Raffaele Giancarlo, Daniela Guaiana:
  On-line Construction of Two-Dimensional Suffix Trees. 72-127
  
• Dong Kyue Kim, Jee-Soo Lee, Kunsoo Park, Yookun Cho:
  Efficient Algorithms for Approximate String Matching with Swaps. 128-147
  
• Yishay Mansour, Noam Nisan, Uzi Vishkin:
  Trade-offs between Communication Throughput and Parallel Time. 148-166
  

Volume 15, Number 2, June 1999

• Hans-Joachim Bungartz, Michael Griebel:
  A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives. 167-199
  
• Z. Huang, Leonid G. Khachiyan, Christopher (Krzysztof) Sikorski:
  Approximating Fixed Points of Weakly Contracting Mappings. 200-213
  
• Felipe Cucker:
  Approximate Zeros and Condition Numbers. 214-226
  
• Pascal Koiran:
  The Real Dimension Problem Is NPR-Complete. 227-238
  
• Jean-Claude Yakoubsohn:
  Finding Zeros of Analytic Functions: alpha Theory for Secant Type Methods. 239-281
  
• Marie-Cécile Darracq:
  Complexity Analysis for Certain Convex Programming Problems. 282-293
  

Volume 15, Number 3, September 1999

• 1998 Best Paper Award. 295-
  
• 1999 Prize for Achievement in Information-Based Complexity. 296-
  
• Year 2000 Prize for Achievement in Information-Based Complexity. 297-
  
• Dagstuhl Invited Papers. 298-
  
• Erich Novak:
  Intractability Results for Positive Quadrature Formulas and Extremal Problems for Trigonometric Polynomials. 299-316
  
• Stefan Heinrich, Eugène Sindambiwe:
  Monte Carlo Complexity of Parametric Integration. 317-341
  
• Christian Lécot, Faysal El Khettabi:
  Quasi-Monte Carlo Simulation of Diffusion. 342-359
  
• Arthur G. Werschulz:
  Where Does Smoothness Count the Most for Two-Point Boundary-Value Problems? 360-384
  
• Sergei V. Pereverzev, Eberhard Schock:
  Brakhage's Implicit Iteration Method and the Information Complexity of Equations with Operators Having Closed Range. 385-401
  
• Grzegorz W. Wasilkowski, Henryk Wozniakowski:
  Weighted Tensor Product Algorithms for Linear Multivariate Problems. 402-447
  

Volume 15, Number 4, December 1999

• Joseph F. Traub:
  From the Editor. 449-
  
• Announcement: Best Paper Award Committee 1999. 450-
  
• Hava T. Siegelmann:
  Stochastic Analog Networks and Computational Complexity. 451-475
  
• Achim Steinbauer:
  Quadrature Formulas for the Wiener Measure. 476-498
  
• Felipe Cucker, Dima Grigoriev:
  Complexity Lower Bounds for Approximation Algebraic Computation Trees. 499-512
  
• Michael Maller, Jennifer Whitehead:
  Efficient p-adic Cell Decompositions for Univariate Polynomials. 513-525
  
• Sui-Xiang Gao, Weili Wu, Ding-Zhu Du, Xiao-Dong Hu:
  The Rivest-Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables. 526-536
  
• Giulia Galbiati, Francesco Maffioli, Carlo Viola:
  Randomized Algorithms over Finite Fields for the Exact Parity Base Problem. 537-556
  
• Tomoyuki Yamakami:
  Polynomial Time Samplable Distributions. 557-574