- Instructors: Victor Chen and Kevin Matulef
- Time: Mon 3:30-5:00, Wed 5:00-6:30
- Place: FIT 1-222

**Course description:**
A *property tester* is a "super-efficient" algorithm that separates objects which have a property from those that are very "different" from having the property. Since the early 1990s, the study of these testers has blossomed into a vibrant field in theoretical computer science. Giving a comprehensive overview of the field is not the goal of this course. Rather, we want to highlight some specific results from this area, so that an adventurous undergraduate or a beginning graduate student can learn enough material to begin working on some research problems.
In particular, in our course, we shall focus on testers that have their inputs represented as Boolean functions, of the form {0,1}^n -> {0,1}.
The analysis of these functions requires many tools in mathematics, most notably in Fourier analysis. In addition to property testing, these tools have led to new results in many other areas, such as additive combinatorics, complexity theory, and computational learning theory. Thus, we will study some of these Fourier-analytic techniques as well.

- Week 0:
- Week 1
- Week 2
- Week 3
- (04/05) No Lecture: Tomb-Sweeping Day
- (04/07) Lecture 7: Roth's Theorem

- Week 3
- (04/12) Lecture 8: Green's arithmetic regularity lemma
- (04/14) Lecture 9: Testing Triangle-freeness in functions

- (04/19) Lecture 10: Noise Sensitivity of Linear Threshold Functions
- (04/21) Lecture 11: Invariance Principle: Majority is Stablest

- Ronitt Rubinfeld's course on Property Testing/Sublinear Time Algorithms (Fall 2004, Spring 2007)
- Ryan O'Donnell's course on Boolean Function Analysis (Spring 2007)
- Ryan O'Donnell's 2008 STOC survey on Boolean Function Analysis (powerpoint slides)
- Ronald de Wolf's survey of Boolean Fourier Analysis (pdf)
- Yishay Mansour's survey on Learning Boolean Functions via the Fourier Transform (gzipped pdf)
- Gil Kalai and Shmuel Safra's survey on Threshold Phenomena and Influences (pdf)

Download the files template.tex and preamble.tex. Put them in the same directory, and use the template.tex file to take your notes. For an example of some scribe notes, see sample-notes.tex.

If you don't have LaTeX up and running on your machine yet, go here for info on getting MacTex, proTeXt, or TeX Live depending on your OS. For editing tex files, I (Kevin) recommend using TeXnicCenter on Windows or TeXShop on the Mac, although Emacs and vim can be made to work well too, if you're into that sort of thing.

A variety of LateX resources are not hard to find on the web.