Local computation and reducibility
Luca Trevisan, Kenji Obata · 2006
A large body of recent work has been concerned with algorithms requiring access to only a sublinear, or even constant, sample of input bits. We study fundamental limitations in this model of computation and relationships to classical problems in combinatorial optimization.