ICS 2011
|
|
Welcome to ICS2011
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 223-238, 978-7-302-24517-9
Tsinghua University Press
For input x, let F(x) denote the set of outputs that are legal answers. Suppose x and members of F(x) are so large that there is not time to read them in their entirety. We propose a model of local computation algorithms which for a given input x, support queries by a user to values of specified locations yi in a legal output y ∈ F(x). When more than one legal output y exists for a given x, the local computation algorithm should output in a way that is consistent with at least one such y. Local computation algorithms are intended to distill the common features of several concepts that have appeared in various algorithmic subfields, including local distributed computation, local algorithms, locally decodable codes, and local reconstruction. We develop a technique, based on Beck's analysis in his algorithmic approach to the Lovász Local Lemma, which under certain conditions can be applied to construct polylogarithmic time local computation algorithms. We apply this technique to maximal independent set computations, scheduling radio network broadcasts, hypergraph coloring and satisfying k-SAT formulas. Preview: 
|
Copyright 2010-2011, Institute for Computer Science, Tsinghua University, All Rights Reserved.