|Lectures:||Tuesday, 14:00 - 16:00, Zoom|
This course offers a graduate introduction to property testing, which studies how to detect structural properties of huge objects by only examining a sub-linear fraction of these objects at random. The goal is to determine if the object has the aforementioned property or is “far” from every object that has the property. The study of such 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.
Some topics: Testing for properties of graphs (triangle freeness, bipartiteness, etc); Testing for properties of distributions ( uniformity/identity, independence, monotonicity, is it a sum of independent variables?); Testing properties of functions (linearity, monotonicity, etc).