6.889 Sublinear Time Algorithms


Graduate Level
Units: 3-0-9
Prerequisites: 6.046, or permission of instructor
Instructor: Professor Ronitt Rubinfeld
Schedule: Lecture TR1-2:30, online instruction
This subjects counts as a Theoretical Computer Science concentration subject. Sublinear Time algorithms understand parameters and properties of input data after viewing only a miniscule fraction of it.  Tools from number theory, combinatorics, linear algebra, optimization theory, distributed algorithms, statistics and probability are covered.  Topics include:   Testing and estimating properties of distributions, functions, graphs, strings, point sets and various combinatorial objects.
More information on how this subject will be taught can be found here