Catalog Description: Topics will vary from semester to semester. See Computer Science Division announcements.
Units: 1.0-4.0
Formats:
Fall: 2.0-6.0 hours of lecture per week
Spring: 1.0-3.0 hours of lecture per week
Grading basis: letter
Final exam status: No final exam
Department Notes: This course offers a graduate introduction to property testing, which studies how to detect structural properties of huge objects by only examining 'local views' of these objects. Property testing has its roots in the program checking and PCP literature, but has evolved into a thriving area of its own standing between algorithms and complexity theory; results are often characterized by relatively simple algorithms that are supported by a fairly complex analysis. Topics covered include testing properties of boolean functions (linearity, dictatorship, juntas), testing algebraic properties of functions (low-degreeness in various settings), testing graph properties (in the dense graph model, bipartiteness, colorability, triangle-freeness), and testing with the aid of provers. Emphasis is on getting students up to speed for research in the area; lectures will often contain open problems or suggestions for future research. The course website is here.