JCSS, Volume 50

Volume 50, Number 1, February 1995

• 
  Konstantinos Kalpakis, Yaacov Yesha:
  On the Power of the Linear Array Architecture for Performing Tree-Structured Computations. 1-10
• 
  Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter:
  Polynomial Size Test Sets for Context-Free Languages. 11-19
• 
  Sally A. Goldman, Michael J. Kearns:
  On the Complexity of Teaching. 20-31
• 
  Avrim Blum, Lisa Hellerstein, Nick Littlestone:
  Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. 32-40
• 
  Efim B. Kinber, Carl H. Smith, Mahendran Velauthapillai, Rolf Wiehagen:
  On Learning Multiple Concepts in Parallel. 41-52
• 
  Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu:
  Decision Problems for Patterns. 53-63
• 
  Ian Parberry:
  Load Sharing with Parallel Priority Queues. 64-73
• 
  Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, Philip M. Long:
  Characterizations of Learnability for Classes of {0, ..., n}-Valued Functions. 74-86
• 
  Klaus Sutner:
  On the Computational Complexity of Finite Cellular Automata. 87
• 
  Naomi Nishimura:
  Efficient Asynchronous Simulation of a Class of Synchronous Parallel Algorithms. 98-113
• 
  Klaus-Uwe Höffgen, Hans Ulrich Simon, Kevin S. Van Horn:
  Robust Trainability of Single Neurons. 114-125
• 
  Adair Dingle, Ivan Hal Sudborough:
  Single Row Routing on Multilayers. 126-131
• 
  Hava T. Siegelmann, Eduardo D. Sontag:
  On the Computational Power of Neural Nets. 132-150
• 
  Jie Wang, Jay Belanger:
  On the NP-Isomorphism Problem with Respect to Random Instances. 151-164
• 
  Minoru Ito, Grant E. Weddell:
  Implication Problems for Functional Constraints on Databases Supporting Complex Objects. 165-187

Volume 50, Number 2, April 1995

Selected Papers from

STOC 1991

• 
  Richard Beigel, Nick Reingold, Daniel A. Spielman:
  PP Is Closed under Intersection. 191-202
• 
  Jirí Matousek:
  Approximations and Optimal Geometric Divide-an-Conquer. 203-208
• 
  Mihalis Yannakakis, David Lee:
  Testing Finite State Machines: Fault Detection. 209-227
• 
  Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas:
  Fast Approximation Algorithms for Multicommodity Flow Problems. 228-243
• 
  Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
  Competitive Paging with Locality of Reference. 244-258
• 
  Harold N. Gabow:
  A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. 259-273
• 
  Erich L. Kaltofen:
  Effective Noether Irreducibility Forms and Applications. 274-295
• 
  László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress:
  Fast Monte Carlo Algorithms for Permutation Groups. 296-308
• 
  Serge Abiteboul, Victor Vianu:
  Computing with First-Order Logic. 309-335
• 
  Dana Angluin, Michael Kharitonov:
  When Won't Membership Queries Help? 336-355

Volume 50, Number 3, June 1995

Selected Papers of the Sixth Annual Conference on Structure in Complexity Theory, June 30 - July 3, 1991

• 
  Richard Chang, Jim Kadin, Pankaj Rohatgi:
  On Unique Satisfiability and the Threshold Behavior of Randomized Reductions. 359-373
• 
  David A. Mix Barrington, Howard Straubing:
  Superlinear Lower Bounds for Bounded-Width Branching Programs. 374-381
• 
  Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri:
  Complexity Classes and Sparse Oracles. 382-390
• 
  Phokion G. Kolaitis, Madhukar N. Thakur:
  Approximation Properties of NP Minimization Classes. 391-411
• 
  Sanjay Gupta:
  Closure Properties and Witness Reduction. 412-432
• 
  Michelangelo Grigni, Michael Sipser:
  Monotone Separation of Logarithmic Space from Logarithmic Depth. 433-437

Selected Papers of the Seventh Annual Conference on Structure in Complexity Theory, June 22-25, 1992

• 
  Martin Beaudry, Pierre McKenzie:
  Circuits, Matrices, and Nonassociative Computation. 441-455
• 
  Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán:
  The Power of the Middle Bit of a #P Function. 456-467
• 
  Ricard Gavaldà:
  Bounding the Complexity of Advice Functions. 468-475
• 
  Pankaj Rohatgi:
  Saving Queries with Randomness. 476-492
• 
  Sanjeev Saluja, K. V. Subrahmanyam, Madhukar N. Thakur:
  Descriptive Complexity of #P Functions. 493-505
• 
  Anne Condon, Richard E. Ladner:
  Interactive Proof Systems with Polynomially Bounded Strategies. 506-518

Selected Papers of the Fifth Annual Workshop on Computational Learning Theory (COLT), July 27-29, 1992

• 
  Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
  Learning Boolean Read-Once Formulas over Generalized Bases. 521-542
• 
  Yishay Mansour:
  An O(n^(log log n)) Learning Algorithm for DNT under the Uniform Distribution. 543-550
• 
  David P. Helmbold, Manfred K. Warmuth:
  On Weak Learning. 551-573
• 
  Robert P. Daley, Bala Kalyanasundaram, Mahendran Velauthapillai:
  Breaking the Probability 1/2 Barrier in FIN-Type Learning. 574-599
• 
  Michael Kharitonov:
  Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution. 600-610