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.

Advisors: 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