Volume 45, Number 1, June 2009

• 
  Paola Flocchini, Andrzej Pelc, Nicola Santoro: Fault-Tolerant Sequential Scan. 1-26
• 
  Daniel Král: Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice. 27-42
• 
  Giovanni Chiola, Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Alberto Negro, Vittorio Scarano: Degree-Optimal Routing for P2P Systems. 43-63
• 
  Jack Jie Dai: An Outer-Measure Approach for Resource-Bounded Measure. 64-73
• 
  Tomasz Jurdzinski: Probabilistic Length-Reducing Two-Pushdown Automata. 74-107
• 
  Jin-yi Cai, Vinay Choudhary, Pinyan Lu: On the Theory of Matchgate Computations. 108-132
• 
  Wit Forys, Piotr Oprocha: Infinite Traces and Symbolic Dynamics. 133-149
• 
  Luis Filipe Coelho Antunes, Lance Fortnow: Sophistication Revisited. 150-161
• 
  George Tsaggouris, Christos D. Zaroliagis: Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications. 162-186

Volume 45, Number 2, August 2009

Special Issue: Symposium on Parallelism in Algorithms and Architectures 2006; Guest Editors: Robert Kleinberg and Christian Scheideler

• 
  Robert D. Kleinberg, Christian Scheideler: Foreword. 187
• 
  François Le Gall: Exponential Separation of Quantum and Classical Online Space Complexity. 188-202
• 
  Matteo Frigo, Volker Strumpen: The Cache Complexity of Multithreaded Cache Oblivious Algorithms. 203-233
• 
  Baruch Awerbuch, Christian Scheideler: Towards a Scalable and Robust DHT. 234-260
• 
  Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir: Tell Me Who I Am: An Interactive Recommendation System. 261-279
• 
  Brighten Godfrey, Richard M. Karp: On the Price of Heterogeneity in Parallel Systems. 280-301
• 
  Ho-Lin Chen, Tim Roughgarden: Network Design with Weighted Players. 302-324
• 
  Ami Litman, Shiri Moran-Schein: Smooth Scheduling under Variable Rates or the Analog-Digital Confinement Game. 325-354
• 
  Costas S. Iliopoulos, Mohammad Sohel Rahman: A New Efficient Algorithm for Computing the Longest Common Subsequence. 355-371
• 
  Vladimir Lipets: Bounds on Mincut for Cayley Graphs over Abelian Groups. 372-380
• 
  Francine Blanchet-Sadri, N. C. Brownstein, Andy Kalcic, Justin Palumbo, T. Weyand: Unavoidable Sets of Partial Words. 381-406
• 
  Sun-Yuan Hsieh, Yu-Fen Weng: Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults. 407-425

Volume 45, Number 3, October 2009

• 
  Thomas Erlebach, Christos Kaklamanis: WAOA 2006 Special Issue of TOCS. 427-428
• 
  Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang: Online Dynamic Programming Speedups. 429-445
• 
  Mark de Berg, Sergio Cabello, Sariel Har-Peled: Covering Many or Few Points with Unit Disks. 446-469
• 
  Vincenzo Bonifaci, Leen Stougie: Online k-Server Routing Problems. 470-485
• 
  Timothy M. Chan, Hamid Zarrabi-Zadeh: A Randomized Algorithm for Online Unit Clustering. 486-496
• 
  Aparna Das, Claire Kenyon-Mathieu: On Hierarchical Diameter-Clustering and the Supplier Problem. 497-511
• 
  Takuro Fukunaga, Hiroshi Nagamochi: Network Design with Edge-Connectivity and Degree Constraints. 512-532
• 
  Tobias Harks, Stefan Heinz, Marc E. Pfetsch: Competitive Online Multicommodity Routing. 533-554
• 
  Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis: Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs. 555-576
• 
  Stephen A. Fenner, William I. Gasarch, Brian Postow: The Complexity of Finding SUBSEQ(A). 577-612
• 
  Sebastian Dörn: Quantum Algorithms for Matching Problems. 613-628
• 
  Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven: On the Black-Box Complexity of Sperner's Lemma. 629-646

Volume 45, Number 4, November 2009

Special Issue: Computation and Logic in the Real World

• 
  S. Barry Cooper, Elvira Mayordomo, Andrea Sorbi: Computation and Logic in the Real World: CiE 2007. 647-649
• 
  Pieter W. Adriaans: Between Order and Chaos: The Quest for Meaningful Information. 650-674
• 
  Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. 675-723
• 
  Luis Filipe Coelho Antunes, Armando Matos, Andre Souto, Paul M. B. Vitányi: Depth as Randomness Deficiency. 724-739
• 
  Laurent Bienvenu, David Doty, Frank Stephan: Constructive Dimension and Turing Degrees. 740-755
• 
  John Case, Samuel E. Moelius: Characterizing Programming Systems Allowing Program Self-Reference. 756-772
• 
  John Case: Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems. 773-786
• 
  Norman Danner, James S. Royer: Two Algorithms in Search of a Type-System. 787-821
• 
  Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. 822-848
• 
  Sanjay Jain, Eric Martin, Frank Stephan: Input-Dependence in Function-Learning. 849-864
• 
  Michal Koucký: Circuit Complexity of Regular Languages. 865-879
• 
  Chung-Chih Li: Speed-Up Theorems in Type-2 Computations Using Oracle Turing Machines. 880-896
• 
  Alexander G. Melnikov: Enumerations and Completely Decomposable Torsion-Free Abelian Groups. 897-916
• 
  Martin Olsen: Nash Stability in Additively Separable Hedonic Games and Community Structures. 917-925
• 
  Mikael Onsjö, Osamu Watanabe: Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions. 926-942
• 
  Mikael Onsjö, Osamu Watanabe: Finding Most Likely Solutions. 943
• 
  Alexandre Pinto: Comparing Notions of Computational Entropy. 944-962
• 
  José Espírito Santo: The lambda-Calculus and the Unity of Structural Proof Theory. 963-994
• 
  Jirí Wiedermann, Lukás Petru: On the Universal Computing Power of Amorphous Computing Systems. 995-1010