Kenji Christopher Obata
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-62
May 17, 2006
http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-62.html %F Obata:EECS-2006-62