6.893 Sub-linear Algorithms


Prereq: 6.046, or permission of instructor
Units: 3-0-9
Schedule: L MW1-2:30, room 24-121
Instructors: Profs. Indyk and Rubinfeld
This subject qualifies as a Theoretical Computer Science Engineering Concentration subject.
Over the last few years data sets have become increasingly massive. As a result, there is a need to design special algorithms and data structures that deal with such amounts of data. In many cases, even linear space/time algorithms can be too slow. Therefore, there has been growing body of work on "sub-linear algorithms", that use space or time that are sub-linear in the input size.
Sub-linear algorithms come in many flavors. In this course we focus on two of them: sub-linear time algorithms, and sketching/streaming algorithms. The former access only a small number of input elements and perform very limited computation; the answer is then inferred using approaches such as random sampling or property testing. The latter extract only a small amount of information about the input (a "sketch") and compute an answer based on that. Manifestation of this approach include data stream algorithms, randomized dimensionality reduction and compressive sensing.
We will cover results from those areas in a unified and systematic manner. On the way, we will introduce the necessary tools from combinatorics, communication complexity, statistics, geometric functional analysis, combinatorial group testing, and other areas.