Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2011/12 / Oberseminar / Thomas Jahn, Complexity and Algorithms in Map-Reduce Models


Inhaltsbereich

Thomas Jahn, Complexity and Algorithms in Map-Reduce Models

TCS Oberseminar, Montag (!), 27.02.2012, 15:00 Uhr
Wann 15:00 15:45 27.02.2012
von bis
Wo L109
Termin übernehmen vCal
iCal

Thomas Jahn
Complexity and Algorithms in Map-Reduce Models

Map Reduce is a programming paradigm used at Google to easily process a massive set of data. Karloff et.al. and Goodrich et.al. introduced models describing Map Reduce from a theoretical point of view. Karloff et.al. defined the complexity class DMRC. We discuss the models, the class DMRC and some weaker definitions of it and their relations to P, NC as well as their subclasses LIN, NC0 and NC1. Based on ideas by Goodrich et.al. we also introduce new complexity classes of problems solvable by Map Reduce algorithms.

Artikelaktionen

abgelegt unter:

Funktionsleiste