Journal of the ACM, Volume 55, 2009

Volume 56, Number 1, January 2009

Kousha Etessami, Mihalis Yannakakis:
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.
Moni Naor, Guy N. Rothblum:
The complexity of online memory checking.
Leslie G. Valiant:
Evolvability.
Moshe Babaioff, Ron Lavi, Elan Pavlov:
Single-value combinatorial auctions and algorithmic implementation in undominated strategies.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning.
Julia Chuzhoy, Sanjeev Khanna:
Polynomial flow-cut gaps and hardness of directed cut problems.
Lars Arvestad, Jens Lagergren, Bengt Sennblad:
The gene evolution model and computing its associated probabilities.
Ran Raz:
Multi-linear formulas for permanent and determinant are of super-polynomial size.
Glencora Borradaile, Philip N. Klein:
An O(n log n) algorithm for maximum st-flow in a directed planar graph.
Markus Püschel, Peter A. Milder, James C. Hoe:
Permuting streaming data using RAMs.

Victor Vianu, Jan Van den Bussche:
Introduction to PODS 2006 special section.
Martin Grohe, André Hernich, Nicole Schweikardt:
Lower bounds for processing data with few random accesses to external memory.
Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin:
Two-variable logic on data trees and XML reasoning.
Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Settling the complexity of computing two-player Nash equilibria.
Jan Remy, Angelika Steger:
A quasi-polynomial time approximation scheme for minimum weight triangulation.
Rajeev Alur, P. Madhusudan:
Adding nesting structure to words.
George S. Lueker:
Improved bounds on the average length of longest common subsequences.
Daniel Stefankovic, Santosh Vempala, Eric Vigoda:
Adaptive simulated annealing: A near-optimal connection between sampling and counting.

Rohit Khandekar, Satish Rao, Umesh V. Vazirani:
Graph partitioning using single commodity flows.
Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes.
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore:
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs.
Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham:
Empirical hardness models: Methodology and a case study on combinatorial auctions.
Tim Roughgarden, Mukund Sundararajan:
Quantifying inefficiency in cost-sharing mechanisms.
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov:
The complexity of obstruction-free implementations.

Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch:
A measure & conquer approach for the analysis of exact algorithms.
Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan:
On the expressiveness and complexity of randomization in finite state monitors.
Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik:
On approximating the ideal random access machine by physical machines.
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
A unified approach to scheduling on unrelated parallel machines.

Leonid Libkin, Victor Vianu:
Introduction to PODS 2007 special section.
Georg Gottlob, Zoltán Miklós, Thomas Schwentick:
Generalized hypertree decompositions: NP-hardness and tractable variants.
Balder ten Cate, Carsten Lutz:
The complexity of query containment in expressive fragments of XPath 2.0.
Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler:
Triangulation and embedding using small sets of beacons.
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
A property of quantum relative entropy with an application to privacy in quantum communication.
Oded Regev:
On lattices, learning with errors, random linear codes, and cryptography.