Journal of the ACM, Volume 54, 2007

Volume 54, Number 1, March 2007

• Martin Grohe:
  The complexity of homomorphism and constraint satisfaction problems seen from the other side.
  Electronic Edition (ACM DL) BibTeX
• Jean-Pierre Jouannaud, Albert Rubio:
  Polymorphic higher-order recursive path orderings.
  Electronic Edition (ACM DL) BibTeX
• Sean Hallgren:
  Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
  Electronic Edition (ACM DL) BibTeX
• Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
  Speed scaling to manage energy and temperature.
  Electronic Edition (ACM DL) BibTeX

Volume 54, Number 2, April 2007

• Sara Cohen, Werner Nutt, Yehoshua Sagiv:
  Deciding equivalences among conjunctive aggregate queries.
  Electronic Edition (ACM DL) BibTeX
• Jos C. M. Baeten, Flavio Corradini, Clemens Grabmayer:
  A characterization of regular expressions under bisimulation.
  Electronic Edition (ACM DL) BibTeX
• Jan A. Bergstra, J. V. Tucker:
  The rational numbers as an abstract data type.
  Electronic Edition (ACM DL) BibTeX
• Vincent Danos, Elham Kashefi, Prakash Panangaden:
  The measurement calculus.
  Electronic Edition (ACM DL) BibTeX
• Dimitris Achlioptas, Frank McSherry:
  Fast computation of low-rank matrix approximations.
  Electronic Edition (ACM DL) BibTeX
• Dimitris Achlioptas, Assaf Naor, Yuval Peres:
  On the maximum satisfiability of random formulas.
  Electronic Edition (ACM DL) BibTeX

Volume 54, Number 3, June 2007

• Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden:
  Approximation via cost sharing: Simpler and better approximation algorithms for network design. 11
  Electronic Edition (ACM DL) BibTeX
• Irit Dinur:
  The PCP theorem by gap amplification. 12
  Electronic Edition (ACM DL) BibTeX
• Arne Andersson, Mikkel Thorup:
  Dynamic ordered sets with exponential search trees. 13
  Electronic Edition (ACM DL) BibTeX
• Vincent Conitzer, Tuomas Sandholm, Jérôme Lang:
  When are elections with few candidates hard to manipulate?. 14
  Electronic Edition (ACM DL) BibTeX
• Joseph Y. Halpern, Riccardo Pucella:
  Characterizing and reasoning about probabilistic and non-probabilistic expectation. 15
  Electronic Edition (ACM DL) BibTeX

Volume 54, Number 4, July 2007

• Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta:
  (Almost) Tight bounds and existence theorems for single-commodity confluent flows.
  Electronic Edition (ACM DL) BibTeX
• Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright:
  A new look at survey propagation and its generalizations.
  Electronic Edition (ACM DL) BibTeX
• Éric Colin de Verdière, Francis Lazarus:
  Optimal pants decompositions and shortest homotopic cycles on an orientable surface.
  Electronic Edition (ACM DL) BibTeX
• Stijn Vansummeren:
  On deciding well-definedness for query languages on trees.
  Electronic Edition (ACM DL) BibTeX
• Tero Harju, Dirk Nowotka:
  Periodicity and unbordered words: A proof of the extended duval conjecture.
  Electronic Edition (ACM DL) BibTeX
• Mark Rudelson, Roman Vershynin:
  Sampling from large matrices: An approach through geometric functional analysis.
  Electronic Edition (ACM DL) BibTeX

Volume 54, Number 5, October 2007

• Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani:
  AdWords and generalized online matching.
  Electronic Edition (ACM DL) BibTeX
• Rafail Ostrovsky, Yuval Rabani:
  Low distortion embeddings for edit distance.
  Electronic Edition (ACM DL) BibTeX
• Thomas Eiter, Kazuhisa Makino:
  On computing all abductive explanations from a propositional Horn theory.
  Electronic Edition (ACM DL) BibTeX
• Andrew Gilpin, Tuomas Sandholm:
  Lossless abstraction of imperfect information games.
  Electronic Edition (ACM DL) BibTeX
• Eijiro Sumii, Benjamin C. Pierce:
  A bisimulation for type abstraction and recursion.
  Electronic Edition (ACM DL) BibTeX

Volume 54, Number 6, December 2007

• Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
  On counting homomorphisms to directed acyclic graphs.
  Electronic Edition (ACM DL) BibTeX
• Mikkel Thorup:
  Equivalence between priority queues and sorting.
  Electronic Edition (ACM DL) BibTeX
• Ling Cheung, Mariëlle Stoelinga, Frits W. Vaandrager:
  A testing scenario for probabilistic processes.
  Electronic Edition (ACM DL) BibTeX
• Faith Ellen, Panagiota Fatourou, Eric Ruppert:
  Time lower bounds for implementations of multi-writer snapshots.
  Electronic Edition (ACM DL) BibTeX
• Sibsankar Haldar, K. Vidyasankar:
  On specification of Read/Write shared variables.
  Electronic Edition (ACM DL) BibTeX
• Nick G. Duffield, Carsten Lund, Mikkel Thorup:
  Priority sampling for estimation of arbitrary subset sums.
  Electronic Edition (ACM DL) BibTeX