Archive for March, 2012

Big news

Thursday, March 15th, 2012

Judea Pearl has won a richly-deserved Turing Award, for his pioneering work on reasoning under uncertainty, Bayesian inference, and causality.  Much like last year’s winner Leslie Valiant, Pearl has been a perfectly-plausible candidate since the 1980s; it was really just a question of when they’d get around to him.  For those who don’t know his work, Pearl’s landmark book Causality provides a wonderful introduction to at least one major strand of his thought; I read it this summer and it inverted the way I think about lots of things in statistics.  (Pearl’s fame precedes this award, partly for a tragic reason: he’s probably best known to the public as the father of the murdered journalist Daniel Pearl.)

In other big news, playing Super Mario Bros. is now known to be NP-complete, as shown in this landmark paper by Greg Aloupis, Erik Demaine, and Alan Guo.  The sheer intuitiveness of the gadget constructions, at least to anyone who grew up playing Nintendo, makes this probably my favorite NP-completeness paper of all time (well, I guess tied with some papers by Cook, Karp, and Levin).