JCSS, Volume 57

Volume 57, Number 1, August 1998

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The Relative Complexity of NP Search Problems. 3-19 BibTeX
Persi Diaconis, Laurent Saloff-Coste: What Do We Know about the Metropolis Algorithm? 20-36 BibTeX
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. 37-49 BibTeX
Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan: Randomized Query Processing in Robot Path Planning. 50-66 BibTeX
Jon M. Kleinberg, Éva Tardos: Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks. 61-73 BibTeX
Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman: Sorting in Linear Time? 74-93 BibTeX
Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya: What's Decidable about Hybrid Automata? 94-124 BibTeX

Eleventh Annual Conference on Structure in Complexity 1996

Manindra Agrawal, Eric Allender, Steven Rudich: Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. 127-143 BibTeX
Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur: Integer Programming as a Framework for Optimization and Approximability. 144-161 BibTeX
Samuel R. Buss, Toniann Pitassi: Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. 162-171 BibTeX
Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay: DNA Models and Algorithms for NP-Complete Problems. 172-186 BibTeX
Uriel Feige, Joe Kilian: Zero Knowledge and the Chromatic Number. 187-199 BibTeX
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer: Nondeterministic NC¹ Computation. 200-212 BibTeX
Dieter van Melkebeek: Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets. 213-232 BibTeX

Anthony J. Bonner, Giansalvatore Mecca: Sequences, Datalog, and Transducers. 234-259 BibTeX
Vinay K. Chaudhri, Vassos Hadzilacos: Safe Locking Policies for Dynamic Databases. 260-271 BibTeX
Mariano P. Consens, Tova Milo: Algebras for Querying Text Regions: Expressive Power and Optimization. 272-288 BibTeX
Guozhu Dong, Jianwen Su: Arity Bounds in First-Order Incremental Evaluation and Definition of Polynomial Time Database Queries. 289-308 BibTeX
Idit Keidar, Danny Dolev: Increasing the Resilience of Distributed and Replicated Database Systems. 309-324 BibTeX
Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. 325-355 BibTeX

Regular Articles

Sanjay Jain: Learning with Refutation. 356-365 BibTeX
Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde: Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth. 366-375 BibTeX
Peter Auer, Philip M. Long, Aravind Srinivasan: Approximating Hyper-Rectangles: Learning and Pseudorandom Sets. 376-388 BibTeX
Eugene Asarin, Oded Maler: Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy. 389-398 BibTeX

Note