Volume 52, Number 1, February 1996

Selected Papers from STOC 1993

• 
  David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer: Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees. 3-27
• 
  Brenda S. Baker: Parameterized Pattern Matching: Algorithms and Applications. 28-42
• 
  Noam Nisan, David Zuckerman: Randomness is Linear in Space. 43-52
• 
  Nicholas Pippenger: Self-Routing Superconcentrators. 53-60

Regular Articles

• 
  Alessandra Cherubini, Pierluigi San Pietro: A Polynomial-Time Parsing Algorithm for K-Depth Languages. 61-79
• 
  Tsong Yueh Chen: On the Structural Properties of the Set of Fixpoints for Nondeterministic Recursive Definitions. 80-86
• 
  Johannes A. La Poutré: Lower Bounds for the Union-Find and the Sp;it-Find Problem on Pointer Machines. 87-99
• 
  Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability. 100-124
• 
  Leonid Libkin, Limsoon Wong: Semantic Representations and Query Labguages for Or-Sets. 125-142
• 
  Egidio Astesiano, Elena Zucca: A Free Construction of Dynamic Terms. 143-156
• 
  Dan E. Willard: Applications of Range Query Theory to Relational Data Base Join and Selection Operations. 157-169
• 
  Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg: Finite Languages for the Representation of Finite Graphs. 170-184
• 
  Juha Honkala: On Parikh Slender Languages and Power Series. 185-190
• 
  Lance Fortnow, Tomoyuki Yamakami: Generic Separations. 191-197

Volume 52, Number 2, April 1996

Sixth Annual Workshop on Computational Learning Theory (COLT), July 26-28, 1993

• 
  Robert E. Schapire, Linda Sellie: Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples. 201-213
• 
  Martin Kummer, Frank Stephan: On the Structure of Degrees of Inferability. 214-238
• 
  Hans-Ulrich Simon: General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts. 239-254
• 
  Sally A. Goldman, H. David Mathias: Teaching a Smarter Learner. 255-267
• 
  Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, Sleiman Matar: Asking Questions to Minimize Errors. 268-286

Regular Articles

• 
  Ajay D. Kshemkalyani: Temporal Interactions of Intervals in Distributed Systems. 287-298
• 
  Amihood Amir, Gary Benson, Martin Farach: Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files. 299-307
• 
  Rainer Schuler, Tomoyuki Yamakami: Structural Average Case Complexity. 308-348
• 
  Vijay K. Vaishnavi: On k-Dimensional Balanced Binary Trees. 328-348
• 
  Gavin J. Gibson: Exact Classification with Two-Layer Neural Nets. 349-356
• 
  Marc Andries, Jan Paredaens: On Instance-Completeness for Database Query Languages involving Object Creation. 357-373
• 
  Shao C. Fang, Santosh S. Venkatesh: Learning Binary Perceptrons Perfectly Efficiently. 374-389

Volume 52, Number 3, June 1996

Seventh Annual Workshop on Computational Learning Theory (COLT) 1994

• 
  Sanjay Jain, Arun Sharma: The Intrinsic Complexity of Language Identification. 393-402
• 
  Martin Kummer, Frank Stephan: Inclusion Problems in Parallel Learning and Games. 403-420
• 
  Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon: Oracles and Queries That Are Sufficient for Exact Learning. 421-433
• 
  Peter L. Bartlett, Philip M. Long, Robert C. Williamson: Fat-Shattering and the Learnability of Real-Valued Functions. 434-452
• 
  David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass: Computing the Maximum Bichromatic Discrepancy with Applications to Computer Graphics and Machine Learning. 453-470
• 
  Michael Frazier, Sally A. Goldman, Nina Mishra, Leonard Pitt: Learning from a Consistently Ignorant Teacher. 471-492

12th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) May 25-27, 1993

• 
  Limsoon Wong: Normal Forms and Conservative Extension Properties for Query Languages over Collection Types. 495-505
• 
  Shinichi Morishita: An Extension of Van Gelder's Alternating Fixpoint to Magic Programs. 506-521
• 
  Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. 522-536
• 
  Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Reflective Programming in the Relational Algebra. 537-549
• 
  Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Selectivity and Cost Estimation for Joins Based on Random Sampling. 550-569
• 
  Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. 570-588
• 
  Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. 589-612