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.
Jean-Pierre Jouannaud, Albert Rubio:
Polymorphic higher-order recursive path orderings.
Sean Hallgren:
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
Speed scaling to manage energy and temperature.

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

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

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.
Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright:
A new look at survey propagation and its generalizations.
Éric Colin de Verdière, Francis Lazarus:
Optimal pants decompositions and shortest homotopic cycles on an orientable surface.
Stijn Vansummeren:
On deciding well-definedness for query languages on trees.
Tero Harju, Dirk Nowotka:
Periodicity and unbordered words: A proof of the extended duval conjecture.
Mark Rudelson, Roman Vershynin:
Sampling from large matrices: An approach through geometric functional analysis.

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

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

Last update Fri May 25 09:28:40 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page