Lecture Notes on Property Testing

(Update: Krzysztof pointed out the resources at sublinear.info, which we forgot to mention. It makes for sense for all of this information to be there. We’ve added links there, and would urge our readers to post more information there. Beats having it in half-baked blogposts!)

Despite the relative maturity of property testing (more than a decade old!), we still lack a good textbook on the subject. At least, I definitely feel the need when I’m talking to interested students. I end up pointing to a bunch of papers, all with their own notation. We now have numerous courses being taught, so that certainly helps. And Oded Goldreich just pointed out his notes. So here’s a summary of stuff that I have found. Please let us know if you have other sources, including your own courses!

Oded Goldreich’s lecture notes
Ronitt Rubinfeld’s collection of surveys
Sofya Raskhodnikova’s course notes at Penn State
Eric Price’s course notes at UT Austin
Grigory Yaroslavtsev’s crash course at the University of Buenos Aires
Rocco Servedio’s course notes at Columbia

5 thoughts on “Lecture Notes on Property Testing

  1. Oded Goldreich

    I guess that at this point I can announce that I intend to write a book on property testing.
    It will be based on the lecture notes, which are already posted.
    The decision grew on me in the last couple of months or so…

    Reply

Leave a Reply to Clement Canonne Cancel reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.