Local Computation and Reducibility
Kenji Christopher Obata
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-62
May 17, 2006
http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-62.pdf
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.
Advisor: Luca Trevisan
BibTeX citation:
@phdthesis{Obata:EECS-2006-62,
Author = {Obata, Kenji Christopher},
Title = {Local Computation and Reducibility},
School = {EECS Department, University of California, Berkeley},
Year = {2006},
Month = {May},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-62.html},
Number = {UCB/EECS-2006-62},
Abstract = {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.}
}
EndNote citation:
%0 Thesis %A Obata, Kenji Christopher %T Local Computation and Reducibility %I EECS Department, University of California, Berkeley %D 2006 %8 May 17 %@ UCB/EECS-2006-62 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-62.html %F Obata:EECS-2006-62