Fast Local Computation Algorithms

Ronitt Rubinfeld, Gil Tamir, Shai Vardi +1

For input $x$, let $F(x)$ denote the set of outputs that are the "legal" answers for a computational problem $F$. Suppose $x$ and members of $F(x)$ are so large that there is not t…