JCSS, Volume 48

Volume 48, Number 1, February 1994

Mihály Geréb-Graus, Ming Li: Three One-Way Heads Cannot Do String Matching. 1-8 BibTeX
Stephen J. Hegner: Unique Complements and Decomposition of Database Schemata. 9-57 BibTeX
Joost Engelfriet, Linda Heyker: Hypergraph Languages of Bounded Degree. 58-89 BibTeX
Guy E. Blelloch, James J. Little: Parallel Solutions to Geometric Problems in the Scan Model of Computation. 90-115 BibTeX
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. 116-148 BibTeX
Jarkko Kari: Reversibility and Surjectivity Problems of Cellular Automata. 149-182 BibTeX
Jin-yi Cai, Anne Condon, Richard J. Lipton: PSPACE Is Provable by Two Provers in One Round. 183-193 BibTeX
Noga Alon, Pavel Pudlák: Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). 194-202 BibTeX

Leong Kwan Li: Learning Fixed Point Patterns by Recurrent Networks. 203-213 BibTeX
Omer Berkman, Uzi Vishkin: Finding Level-Ancestors in Trees. 214-230 BibTeX
Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk: Exact Lower Time Bounds for Computing Boolean Functions on CREW PRAMs. 231-254 BibTeX
Marco Cadoli, Maurizio Lenzerini: The Complexity of Propositional Closed World Reasoning and Circumscription. 255-310 BibTeX
Gyora M. Benedek, Alon Itai: Nonuniform Learnability. 311-323 BibTeX
Steven Homer, Luc Longpré: On Reductions of NP Sets to Sparse Sets. 324-336 BibTeX
Douglas R. Stinson: Combinatorial Techniques for Universal Hashing. 337-346 BibTeX
Kai-Yeung Siu, Amir Dembo, Thomas Kailath: On the Perceptron Learning Algorithm on Data with High Precision. 347-356 BibTeX
Alan L. Selman: A Taxonomy of Complexity Classes of Functions. 357-381 BibTeX

Selected Papers of FOCS 1990

Marshall W. Bern, David Eppstein, John R. Gilbert: Provably Good Mesh Generation. 384-409 BibTeX
Amos Fiat, Yuval Rabani, Yiftach Ravid: Competitive k-Server Algorithms. 410-428 BibTeX
C. Andrew Neff: Specified Precision Polynomial Root Isolation Is in NC. 429-463 BibTeX
Michael J. Kearns, Robert E. Schapire: Efficient Distribution-Free Learning of Probabilistic Concepts. 464-497 BibTeX
Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. 498-532 BibTeX
Michael L. Fredman, Dan E. Willard: Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths. 533-551 BibTeX