Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 53 Issue 6, November 2006

On the composition of authenticated Byzantine Agreement
Yehuda Lindell, Anna Lysyanskaya, Tal Rabin
Pages: 881-917
DOI: 10.1145/1217856.1217857
A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research....

Linear work suffix array construction
Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt
Pages: 918-936
DOI: 10.1145/1217856.1217858
Suffix trees and suffix arrays are widely used and largely interchangeable index structures on strings and sequences. Practitioners prefer suffix arrays due to their simplicity and space efficiency while theoreticians use suffix trees due to...

Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T)
Robert Nieuwenhuis, Albert Oliveras, Cesare Tinelli
Pages: 937-977
DOI: 10.1145/1217856.1217859
We first introduce Abstract DPLL, a rule-based formulation of the Davis--Putnam--Logemann--Loveland (DPLL) procedure for propositional satisfiability. This abstract framework allows one to cleanly express practical DPLL algorithms and to...

An approximation scheme for stochastic linear programming and its application to stochastic integer programs
David B. Shmoys, Chaitanya Swamy
Pages: 978-1012
DOI: 10.1145/1217856.1217860
Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional...