Monday, April 12, Volen 101, 11-12pm (Refreshments at 11:00pm)
We have long considered showing the existence of a linear time algorithm for a problem to be the gold standard of achievement. Indeed, it is hard to imagine doing any better than that, since for most nontrivial problems, any algorithm must consider all of the input in order to make a decision. However, as extremely large data sets grow more prevalent in a variety of settings, it is natural to wonder what one can do in *sublinear* time. In fact, there has been a lot of recent interest in this direction. For most natural problems a sublinear time algorithm must necessarily give some type of an approximate answer. However, there are many situations in which a fast approximate solution is more useful than a slower exact solution. This talk will survey a number of problems that can be solved in sublinear time, using different types of approximations. The problems come from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory.
Host: Liuba Shrira