Volume 54, Number 1, February 1997

11th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) June 2-4, 1992

• 
  Catriel Beeri, Tova Milo: Comparison of Functional and Predicative Query Paradigms. 3-33
• 
  Jan Van den Bussche, Dirk Van Gucht: A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries. 34-47
• 
  Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. 48-60
• 
  Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. 61-78
• 
  Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Database. 79-97
• 
  Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. 98-112
• 
  Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. 113-135
• 
  Anthony J. Bonner, Tomasz Imielinski: Reusing and Modifying Rulebases by Predicate Substitution. 136-166

1st Annual Dagstuhl Seminar on Neural Computing (DSNC) November 7-11, 1994

• 
  Marek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. 169-176
• 
  Pascal Koiran: A Weak Version of the Blum, Shub, and Smale Model. 177-189
• 
  Pascal Koiran, Eduardo D. Sontag: Neural Networks with Quadratic VC Dimension. 190-198
• 
  György Turán, Farrokh Vatan: On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In. 199-212

Volume 54, Number 2, April 1997

32nd Annual Symposium on Foundations of Computer Science October 2-4, 1991

• 
  Dror Lapidot, Adi Shamir: Fully Parallelized Multi-Prover Protocols for NEXP-Time. 215-220
• 
  Jaikumar Radhakrishnan: Better Lower Bounds for Monotone Threshold Formulas. 221-226
• 
  Donald B. Johnson, Panagiotis Takis Metaxas: Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM. 227-242
• 
  Zvi Galil, Oded Margalit: All Pairs Shortest Paths for Graphs with Small Integer Length Edges. 243-254
• 
  Noga Alon, Zvi Galil, Oded Margalit: On the Exponent of the All Pairs Shortest Path Problem. 255-262

32nd Annual Symposium on Foundations of Computer Science November 3-5, 1993

• 
  Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton: Breaking the Theta (n log² n) Barrier for Sorting with Faults. 265-304
• 
  Uriel Feige: A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity. 305-316
• 
  Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk: The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. 317-331
• 
  Charles E. Leiserson, Satish Rao, Sivan Toledo: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers. 332-344
• 
  Amir M. Ben-Amram: When Can We Sort in o(n log n) Time? 345-370
• 
  Avrim Blum, Ravindran Kannan: Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution. 371-380

Volume 54, Number 3, June 1997

Tenth Annual Conference on Structure in Complexity 1995

• 
  Manindra Agrawal: DSPACE(n) = NSPACE(n): A Degree Theoretic Characterization. 383-392
• 
  Harry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. 393-399
• 
  Kousha Etessami: Counting Quantifiers, Successor Relations, and Logarithmic Space. 400-411
• 
  John D. Rogers: The Isomorphism Conjecture Holds and One-Way Functions Exists Relative to an Oracle. 412-423
• 
  James S. Royer: Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals. 424-436
• 
  Nicholas Q. Trân: On P-Immunity of Exponential Time Complete Sets. 437-440

Regular Articles

• 
  Domenico Saccà: The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries. 441-464
• 
  Liming Cai, Jianer Chen: On Fixed-Parameter Tractability and Approximability of NP Optimization Problems. 465-474
• 
  Yosi Ben-Asher, Ilan Newman: Geometric Approach for Optimal Routing on a Mesh with Buses. 475-486
• 
  H. David Mathias: A Model of Interactive Teaching. 487-501
• 
  Karl Meinke: A Completeness Theorem for the Expressive Power of Higher-Order Algebraic Specifications. 502-519