Who Says You Have to Look at the Input? The Brave New World of Sublinear
Bernard Chazelle, Princeton University and NEC Laboratories America, Inc.
Surprisingly often, a computational problem will come up for which sampling a vanishing fraction of the input is sufficient to obtain excellent approximate answers. How is that possible? Which sort of problems fall into that category? What are the techniques known to make this "sublinearity" phenomenon happen? This talk will address each of these questions briefly by looking at specific examples.
Return to Program