Course Identification
Introduction to Property Testing
Lecturers and Teaching Assistants
Dr. Reut Levi, Prof. Oded Goldreich
Course Schedule and Location
Thursday, 11:15 - 13:00, Goldsmith, room 108
08/11/2018
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; 2.00 points
Attendance and participation
Estimated Weekly Independent Workload (in hours)
Syllabus
Property Testing is concerned with approximate decisions, where the task is distinguishing between objects having a predetermined property and objects that are ``far'' from having this property. Typically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms that may query the function at arguments of their choice, and seek algorithms of very low complexity (i.e., much lower than the size of the function's domain).
Specific topics will include:
- Testing graph properties:
- in the adjacency matrix model (subgraph freeness, bipartiteness),
- the bounded-degree model (one-sided error bipartiteness, two-sided error cycle-freeness, partition oracles)
- the general graph model (bounded arboricity)
- Testing algebraic properties (linearity)
- Testing properties of Boolean functions (monotonicity, dictatorship, juntas)
- Testing properties of distributions (uniformity, identity, monotonicity, lower bound technique via matching moments)
- Property testing in the Congest model
Learning Outcomes
Upon successful completion of this course students should be able to:
- Describe the key notions and principles of the area of property testing.
- Demonstrate familiarity with basic paradigms and techniques of the area of property testing.
- Apply notions, principles, paradigms, and techniques of property testing to their own research.
- Discuss the meaning of the various notions and results of property testing.
Reading List
We shall use Oded's textbook Introduction to Property Testing (Cambridge Uni. Press, 2017). Drafts of the text are available from the book's website http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html