Fundamenta Informaticae · 2011 · 13 citations · 21 references
ComputingComputer ScienceAlgorithmsCluster ComputingParallel ComputingDistributed ComputingRandomized AlgorithmsRandomized ComplexityRandomized ComputationBoolean SatisfiabilityBoolean Satisfiability ProblemPartitioning ProblemsRandomized SearchRandomized Search AlgorithmsSatisfiabilitySatisfiability Problem
This paper studies the following question: given an instance of the propositional satisfiability problem, a randomized satisfiability solver, and a cluster of n computers, what is the best way to use the computers to solve the instance? Two approache
21
Carla P. Gomes, Bart Selman · Artificial Intelligence · 2001 · 448 citations
An Economics Approach to Hard Computational Problems
Bernardo A. Huberman, Rajan M. Lukose, Tad Hogg · Science · 1997 · 385 citations
Optimal speedup of Las Vegas algorithms
Michael Luby, Alistair Sinclair, David Zuckerman · 2002 · 362 citations