dblp: Journal of Complexity, Volume 15

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

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

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

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

Journal of Complexity, Volume 15

Volume 15, Number 1, March 1999

Volume 15, Number 2, June 1999

Volume 15, Number 3, September 1999

Volume 15, Number 4, December 1999