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