New techniques and tighter bounds for local computation algorithms.

Given an input x and a search problem F , local computation algorithms (LCAs) implement access to specified locations of y in a legal output y ∈ F ( x ) , using polylogarithmic time and space. Parnas and Ron [27] and Mansour et al. [19] showed how to convert certain distributed and online algorithms to LCAs, respectively. In this work, we expand on those lines of work and develop new techniques for designing LCAs and bounding their space and time complexity. [ABSTRACT FROM AUTHOR]