Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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