JCSS, Volume 55

Volume 55, Number 1, August 1997

• Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian:
  Faster Shortest-Path Algorithms for Planar Graphs. 3-23
  
• Alexander A. Razborov, Steven Rudich:
  Natural Proofs. 24-35
  
• Andrew Chi-Chih Yao:
  Decision Tree Complexity and Betti Numbers. 36-43
  
• Ramesh Hariharan:
  Optimal Parallel Suffix Tree Construction. 44-69
  

• Ray J. Solomonoff:
  The Discovery of Algorithmic Probability. 73-88
  
• Jorma Rissanen:
  Stochastic Complexity in Learning. 89-95
  
• V. G. Vovk:
  Learning about the Parameter of the Bernoulli Model. 96-104
  
• Kenji Yamanishi:
  On-Line Maximum Likelihood Prediction with Respect to General Loss Functions. 105-118
  
• Yoav Freund, Robert E. Schapire:
  A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. 119-139
  
• Dale Schuurmans:
  Characterizing Rational Versus Exponential learning Curves. 140-160
  
• Leonid Gurvits, Pascal Koiran:
  Approximation and Learning of Convex Superpositions. 161-170
  
• Shai Ben-David, Michael Lindenbaum:
  Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher. 171-182
  
• John Case, Susanne Kaufmann, Efim B. Kinber, Martin Kummer:
  Learning Recursive Functions from Approximations. 183-196
  

Volume 55, Number 2, October 1997

• Sushant Patnaik, Neil Immerman:
  Dyn-FO: A Parallel, Dynamic Complexity Class. 199-209
  
• Foto N. Afrati:
  Bounded Arity Datalog (not-)Queries on Graphs. 210-228
  
• Christos Faloutsos, Ibrahim Kamel:
  Relaxing the Uniformity and Independence Assumptions Using the Concept of Fractal Dimension. 229-240
  
• Leonid Libkin, Limsoon Wong:
  Query Languages for Bags and Aggregate Functions. 241-272
  
• Stéphane Grumbach, Jianwen Su:
  Finitely Representable Databases. 273-298
  
• Dan Suciu, Val Tannen:
  A Query Language for NC. 299-321
  
• Dan Suciu, Jan Paredaens:
  The Complexity of the Evaluation of Complex Algebra Expressions. 322-343
  
• Vashudha Krishnaswamy, Divyakant Agrawal, John L. Bruno, Amr El Abbadi:
  Relative Serializability: An Approach for Relaxing the Atomicity of Transactions. 344-354
  
• Surajit Chaudhuri, Phokion G. Kolaitis:
  Can Datalog Be Approximated? 355-369
  

Volume 55, Number 3, December 1997

• Rakesh K. Sinha, Jayram S. Thathachar:
  Efficient Oblivious Branching Programs for Threshold and Mod Functions. 373-384
  
• Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma:
  On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates. 385-401
  
• David R. Karger, Daphne Koller:
  (De)randomized Construction of Small Sample Spaces in NC. 402-413
  
• Jeffrey C. Jackson:
  An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. 414-440
  
• Edith Cohen:
  Size-Estimation Framework with Applications to Transitive Closure and Reachability. 441-453
  
• Karsten Weihe: Maximum (s, t)-Flows in Planar Networks in O(|V|log|V|)-Time. 454-476

• Jean Berstel, Luc Boasson:
  The Set of Minimal Words of a Context-Free Language is Context-Free. 477-488
  
• Joost Engelfriet, Vincent van Oostrom:
  Logical Description of Contex-Free Graph Languages. 489-503
  
• Joan Boyar, Rolf Fagerberg, Kim S. Larsen:
  Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. 504-521
  
• Eddy Fromentin, Michel Raynal:
  Shared Global States in Distributed Computations. 522-528
  
• G. Y. Yan, Andreas Alexander Albrecht, G. H. F. Young, Chak-Kuen Wong:
  The Steiner Tree Problem in Orientation Metrics. 529-546
  
• Lane A. Hemaspaandra, Mitsunori Ogihara:
  Universally Serializable Computation. 547-560
  

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