Journal of Complexity, Volume 13

Volume 13, Number 1, March 1997

• Joseph F. Traub:
  Best Paper Award. 1-
  
• Michael Shub:
  Guest Editor's Introduction. 2-3
  
• Bernd Bank, Marc Giusti, Joos Heintz, Guy M. Mbakop:
  Polar Varieties, Real Equation Solving, and Data Structures: The Hypersurface Case. 5-27
  
• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  On Computing a Set of Points Meeting Every Cell Defined by a Family of Polynomials on a Variety. 28-37
  
• Walter Baur:
  Simplified Lower Bounds for Polynomials with Algebraic Coefficients. 38-41
  
• Don Coppersmith:
  Rectangular Matrix Multiplication Revisited. 42-49
  
• Dima Grigoriev:
  Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations. 50-64
  
• Pascal Koiran:
  Elimination of Constants from Machines over Algebraically Closed Fields. 65-82
  
• Thomas Lickteig, Klaus Meer:
  Semi-algebraic Complexity--Additive Complexity of Matrix Computational Tasks. 83-107
  
• Victor Y. Pan, Ailong Zheng, Xiaohan Huang, Olen Dias:
  Newton's Iteration for Inversion of Cauchy-Like and Other Structured Matrices. 108-124
  
• Charles Pugh, Michael Shub:
  Stably Ergodic Dynamical Systems and Partial Hyperbolicity. 125-179
  
• Madhu Sudan:
  Decoding of Reed Solomon Codes beyond the Error-Correction Bound. 180-193
  

Volume 13, Number 2, June 1997

• Michael Maller, Jennifer Whitehead:
  Computational Complexity over thep-adic Numbers. 195-207
  
• Israel Gohberg, Vadim Olshevsky:
  The Fast Generalized Parker-Traub Algorithm for Inversion of Vandermonde and Related Matrices. 208-234
  
• Ronald Cools, Andrew V. Reztsov:
  Different Quality Indexes for Lattice Rules. 235-258
  
• Christine Gaßner:
  On NP-Completeness for Linear Machines. 259-271
  
• Misako Yokoyama:
  Computing the Topological Degree with Noisy Information. 272-278
  
• Valentin E. Brimkov, Stefan S. Dantchev:
  Real Data--Integer Solution Problems within the Blum-Shub-Smale Computational Model. 279-300
  

Volume 13, Number 3, September 1997

• Best Paper Award. 301-
  
• Ernst W. Mayr:
  Some Complexity Results for Polynomial Ideals. 303-325
  
• Alberto Bertoni, Paola Campadelli, Cristina Gangai, Roberto Posenato:
  Approximability of the Ground State Problem for Certain Ising Spin Glasses. 326-329
  
• Yair Caro, Raphael Yuster:
  Recognizing Global Occurrence of Local Properties. 340-352
  
• Harald Niederreiter, Michael Vielhaber:
  Linear Complexity Profiles: Hausdorff Dimensions for Almost Perfect Profiles and Measures for General Profiles. 353-383
  

Volume 13, Number 4, December 1997

• Joseph F. Traub:
  A Note from the Editor. 385-
  
• Erich Novak:
  Editor's Foreword: Dagstuhl Invited Papers. 386-
  
• Erich Novak, Ian H. Sloan, Henryk Wozniakowski:
  Tractability of Tensor Product Linear Operators. 387-418
  
• Gianna M. Del Corso, Giovanni Manzini:
  On the Randomized Error of Polynomial Methods for Eigenvector and Eigenvalue Estimates. 419-456
  
• Arthur G. Werschulz:
  The Complexity of Indefinite Elliptic Problems with Noisy Data. 457-479
  
• Nicholas N. Vakhania:
  Polya's Characterization Theorem for Complex Random Variables. 480-488
  
• Ronald A. DeVore, Vladimir N. Temlyakov:
  Nonlinear Approximation in Finite-Dimensional Spaces. 489-508
  
• Joel Ratsaby, Vitaly Maiorov:
  On the Value of Partial Information for Learning from Examples. 509-543