Who says you have to look at the input? The brave new world of sublinear computing.

Bernard Chazelle

Browse the full SODA paper archive.