- 2007
- Dimitris Achlioptas, Frank McSherry:
Fast computation of low-rank matrix approximations. J. ACM 54(2): 9 (2007) - Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the maximum satisfiability of random formulas. J. ACM 54(2): 10 (2007) - Arne Andersson, Mikkel Thorup:
Dynamic ordered sets with exponential search trees. J. ACM 54(3): 13 (2007) - Jos C. M. Baeten, Flavio Corradini, Clemens Grabmayer:
A characterization of regular expressions under bisimulation. J. ACM 54(2): 6 (2007) - Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
Speed scaling to manage energy and temperature. J. ACM 54(1): 3:1-3:39 (2007) - Jan A. Bergstra, John V. Tucker:
The rational numbers as an abstract data type. J. ACM 54(2): 7 (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. J. ACM 54(4): 16 (2007) - Ling Cheung, Mariëlle Stoelinga
, Frits W. Vaandrager:
A testing scenario for probabilistic processes. J. ACM 54(6): 29 (2007) - Sara Cohen
, Werner Nutt
, Yehoshua Sagiv:
Deciding equivalences among conjunctive aggregate queries. J. ACM 54(2): 5 (2007) - Vincent Conitzer, Tuomas Sandholm, Jérôme Lang:
When are elections with few candidates hard to manipulate?. J. ACM 54(3): 14 (2007) - Vincent Danos, Elham Kashefi, Prakash Panangaden:
The measurement calculus. J. ACM 54(2): 8 (2007) - Irit Dinur
:
The PCP theorem by gap amplification. J. ACM 54(3): 12 (2007) - Nick G. Duffield
, Carsten Lund, Mikkel Thorup:
Priority sampling for estimation of arbitrary subset sums. J. ACM 54(6): 32 (2007) - Martin E. Dyer
, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): 27 (2007) - Thomas Eiter, Kazuhisa Makino:
On computing all abductive explanations from a propositional Horn theory. J. ACM 54(5): 24 (2007) - Faith Ellen, Panagiota Fatourou, Eric Ruppert:
Time lower bounds for implementations of multi-writer snapshots. J. ACM 54(6): 30 (2007) - Andrew Gilpin, Tuomas Sandholm:
Lossless abstraction of imperfect information games. J. ACM 54(5): 25 (2007) - Martin Grohe
:
The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1): 1:1-1:24 (2007) - Anupam Gupta, Amit Kumar
, Martin Pál, Tim Roughgarden:
Approximation via cost sharing: Simpler and better approximation algorithms for network design. J. ACM 54(3): 11 (2007) - Sibsankar Haldar, K. Vidyasankar:
On specification of Read/Write shared variables. J. ACM 54(6): 31 (2007) - Sean Hallgren:
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM 54(1): 4:1-4:19 (2007) - Joseph Y. Halpern, Riccardo Pucella:
Characterizing and reasoning about probabilistic and non-probabilistic expectation. J. ACM 54(3): 15 (2007) - Tero Harju
, Dirk Nowotka:
Periodicity and unbordered words: A proof of the extended duval conjecture. J. ACM 54(4): 20 (2007) - Jean-Pierre Jouannaud, Albert Rubio:
Polymorphic higher-order recursive path orderings. J. ACM 54(1): 2:1-2:48 (2007) - Elitza N. Maneva
, Elchanan Mossel
, Martin J. Wainwright
:
A new look at survey propagation and its generalizations. J. ACM 54(4): 17 (2007) - Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani:
AdWords and generalized online matching. J. ACM 54(5): 22 (2007) - Rafail Ostrovsky, Yuval Rabani:
Low distortion embeddings for edit distance. J. ACM 54(5): 23 (2007) - Mark Rudelson, Roman Vershynin:
Sampling from large matrices: An approach through geometric functional analysis. J. ACM 54(4): 21 (2007) - Eijiro Sumii, Benjamin C. Pierce:
A bisimulation for type abstraction and recursion. J. ACM 54(5): 26 (2007) - Mikkel Thorup:
Equivalence between priority queues and sorting. J. ACM 54(6): 28 (2007)