Research Seminar: Property Testing from a Fourier-analytic perspective

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.

Schedule

References

A few pointers to related courses/surveys

Instructions for scribes

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.