enter search term and/or author name
On the composition of authenticated Byzantine Agreement
Yehuda Lindell, Anna Lysyanskaya, Tal Rabin
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
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
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
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...