Séminaire du 11 avril 05, by Bernard Chazelle, Princeton University
The traditional view of computing puts the spotlight on the output rather than on the input. The main reason for this -- besides the obvious one, which is that the input is what we have but the output is what we want -- is that computational power is often gained by lowering our expectations about the output side of the computing pipeline (think of randomization, approximation, etc). A shift in focus toward the "input" has occurred lately, however, causing a revolution of sorts in algorithm design. Computing with massive data sets, data streaming, coping with uncertainty, priced computation, property testing, and sublinear algorithms are all parts of the story. I will discuss the past and present of this development and speculate about its future; all in the (biased) context of my own research.