Volume 22, Numbers 1/2, September/October 1998

Computational Learning Theory

• 
  Shai Ben-David: Can Finite Samples Detect Singularities of Reao-Valued Functions? 3-17
• 
  Douglas A. Cenzer, William R. Moser: A Good Oracle Is Hard to Beat. 18-34
• 
  Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. 35-52
• 
  Stephen Kwek, Leonard Pitt: PAC Learning Intersections of Halfspaces with Membership Queries. 53-75
• 
  Amos Beimel, Eyal Kushilevitz: Learning Boxes in High Dimension. 76-90
• 
  Nader H. Bshouty, Christino Tamon, David K. Wilson: Learning Matrix Functions over Rings. 91-111
• 
  Nicolò Cesa-Bianchi, David P. Helmbold, Sandra Panizza: On Bayes Methods for On-Line Boolean Prediction. 112-137
• 
  K. Hiraoka, Shun-ichi Amari: Strategy Under the Unknown Stochastic Environment: The Nonparametric Lob-Pass Problem. 138-156
• 
  John Shawe-Taylor: Classification Accuracy Based on Observed Margin. 157-172
• 
  R. Kamimura: Minimizing alpha-Information for Generalization and Interpretation. 173-197
• 
  Stefan M. Rüger: A Class of Asymptotically Stable Algorithms for Learning-Rate Adaptation. 198-210
• 
  Alex J. Smola, Bernhard Schölkopf: On a Kernel-Based Method for Pattern Recognition, Regression, Approximation, and Operator Inversion. 211-231

Volume 22, Number 3, 1998

• 
  Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. 235-249
• 
  Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni: Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees. 250-274
• 
  Giuseppe F. Italiano, Rajiv Ramaswami: Maintaining Spanning Trees of Small Diameter. 275-304
• 
  Bala Swaminathan, Kenneth J. Goldman: An Incremental Distributed Algorithm for Computing Biconnected Components in Dynamic Graphs. 305-329
• 
  Greg N. Frederickson: Maintaining Regular Properties Dynamically in k-Terminal Graphs. 330-350
• 
  Monika Rauch Henzinger, Michael L. Fredman: Lower Bounds for Fully Dynamic Connectivity Problems in Graphs. 351-362

Volume 22, Number 4, 1998

Average-Case Analysis of Algorithms

• 
  Helmut Prodinger, Wojciech Szpankowski: Philippe Flajolet's Research in Analysis of Algorithms and Combinatorics. 366-387
• 
  David Aldous: A. Metropolis-Type Optimization Algorithm on the Infinite Tree. 388-412
• 
  F. Thomas Bruss, Michael Drmota, Guy Louchard: The Complete Solution of the Competitive Rank Selection Problem. 413-447
• 
  Edward G. Coffman Jr., Leopold Flatto, Predrag R. Jelenkovic, Bjorn Poonen: Packing Random Intervals On-Line. 448-476
• 
  Luc Devroye, Ernst P. Mücke, Binhai Zhu: A Note on Point Location in Delaunay Triangulations of Random Points. 477-482
• 
  Wenceslas Fernandez de la Vega, Alan M. Frieze, Miklos Santha: Average-Case Analysis of the Merging Algorithm of Hwang and Lin. 483-489
• 
  Philippe Flajolet, Patricio V. Poblete, Alfredo Viola: On the Analysis of Linear Probing Hashing. 490-515
• 
  Micha Hofri, Philippe Jacquet: Saddle Points in Random Matrices: Analysis of Knuth Search Algorithms. 516-528
• 
  Hsien-Kuei Hwang: Asymptotics of Divide-and-Conquer Recurrences: Batcher's Sorting Algorithm and a Minimum Euclidean Matching Heuristic. 529-546
• 
  Charles Knessl: A Note on the Asymptotic Behavior of the Depth of Tries. 547-560
• 
  Donald E. Knuth: Linear Probing and Graphs. 561-568
• 
  Hosam M. Mahmoud, Robert T. Smythe: Probabilistic Analysis of MULTIPLE QUICK SELECT. 569-584
• 
  Donatella Merlini, Renzo Sprugnoli, M. Cecilia Verri: Average-Case Analysis for a Simple Compression Algorithm. 585-599
• 
  Alois Panholzer, Helmut Prodinger: Average-Case Analysis of Priority Trees: A Structure for Priority Queue Administration. 600-630
• 
  Mireille Régnier, Wojciech Szpankowski: On Pattern Frequency Occurrences in a Markovian Sequence. 631-649
• 
  Hadas Shachnai, Micha Hofri: The List Update Problem: Improved Bounds for the Counter Scheme. 650-659
• 
  Brigitte Vallée: Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators. 660-685