## What, if anything, can be done in linear time?

Microsoft Research, Redmond, WA

Tuesday, 29 April 2014, 14:00 (note the unusual weekday)

Cybernetica Bldg (Akadeemia tee 21), room B126

Slides from the talk [pdf]

**Abstract**: The answer to the title question seems to be "Not
much." Even sorting *n* items takes *n log n* swaps. In
fact, quite a bit can be done in linear time. We start with an
illustration of linear-time techniques. Then we sketch the linear-time
decision algorithm for propositional primal infon logic. Finally we
mention useful extensions of that logic decidable in deterministic or
probabilistic linear time.

Tarmo Uustalu

Last update 16.4.2014