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.