2008.08.11 | Else Magård

Titel: Blasting Transdichotomous Atomic Rambo

Speaker: John Iacono, Polytechnic Institute of New York University

Abstract:
Suppose you have a fixed set of n numbers and you want to create a data
structure that allows a fast search in this set. How fast can such a search be?
Well it depends on what computer you have. But theoreticians don't have
computers, instead we have models of computation. But what is a model of
computation other that saying what things you can do in what amount of time?
Being able to set the rules by which our algorithms are evaluated should make
it easier to design fast algorithms. Traditionally, models of computation have
had some relation to actual computers, but insisting on this relationship can
result in slower algorithms than if one is unconstrained by reality. In particular,
we discuss how non-standard, but plausible, CPU and memory designs can
allow the design of asymptotically faster fundamental algorithms.

Host: Lars Arge