JCSS, Volume 75

Volume 75, Number 1, January 2009

• Lisa Hellerstein, Hans-Ulrich Simon:
  Special Issue: Learning Theory 2006. 1
  
• Adam R. Klivans, Alexander A. Sherstov:
  Cryptographic hardness for learning intersections of halfspaces. 2-12
  
• Vitaly Feldman:
  Hardness of approximate two-level logic minimization and PAC learning with membership queries. 13-26
  
• Lance Fortnow, Adam R. Klivans:
  Efficient learning algorithms yield circuit lower bounds. 27-36
  
• Benjamin I. P. Rubinstein, Peter L. Bartlett, J. Hyam Rubinstein:
  Shifting: One-inclusion mistake bounds and sample compression. 37-59
  
• Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu:
  Learning a circuit by injecting values. 60-77
  
• Maria-Florina Balcan, Alina Beygelzimer, John Langford:
  Agnostic active learning. 78-89
  

Volume 75, Number 2, February 2009

• Jonathan Katz, Chiu-Yuen Koo:
  On expected constant-round protocols for Byzantine agreement. 91-112
  
• Lila Kari, Shinnosuke Seki:
  On pseudoknot-bordered words and their properties. 113-121
  
• Leah Epstein, Asaf Levin:
  Better bounds for minimizing SONET ADMs. 122-136
  
• Meena Mahajan, Venkatesh Raman, Somnath Sikdar:
  Parameterizing above or below guaranteed values. 137-153
  

Volume 75, Number 3, May 2009

• Chaim Linhart, Ron Shamir:
  Faster pattern matching with character classes using prime number encoding. 155-162
  
• Felix Brandt, Felix A. Fischer, Markus Holzer:
  Symmetries and the complexity of pure Nash equilibrium. 163-177
  
• Cristian Martín, Mikel Larrea, Ernesto Jiménez:
  Implementing the Omega failure detector in the crash-recovery failure model. 178-189
  
• Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
  The power of verification for one-parameter agents. 190-211
  

Volume 75, Number 4, June 2009

• Andrea E. F. Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri:
  Broadcasting in dynamic radio networks. 213-230
  
• Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos:
  Derivation of algorithms for cutwidth and related graph layout parameters. 231-244
  
• Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
  The complexity of satisfiability problems: Refining Schaefer's theorem. 245-254
  
• Harumichi Nishimura, Tomoyuki Yamakami:
  An application of quantum finite automata to interactive proof systems. 255-269
  

Volume 75, Number 5, August 2009

• Joost Engelfriet, Sebastian Maneth, Helmut Seidl:
  Deciding equivalence of top-down XML transformations in polynomial time. 271-286
  
• Mary V. Ashley, Tanya Y. Berger-Wolf, Piotr Berman, Wanpracha Art Chaovalitwongse, Bhaskar DasGupta, Ming-Yang Kao:
  On approximating four covering and packing problems. 287-302
  
• Sherif Sakr:
  XML compression techniques: A survey and comparison. 303-322