6.5240 Sublinear Time Algorithms

This course will focus on the design of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the data. The study of sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms. Topics include: Estimating parameters and properties of graphs (average degree, min vertex cover, MST, max matching, number of connected components, diameter, clusterability, bipartiteness); Sublinear time and local access to optimization solutions (coloring, maximal independent set); Estimating parameters and properties of distributions (entropy, support size, independence, uniformity, independence, monotonicity, is it a sum of independent variables?); Estimating properties of functions (linearity and low degree polynomial testing, monotonicity, linear threshold functions, number of relevant variables).

Course website: https://people.csail.mit.edu/ronitt/COURSE/F24/