Course Identification

Introduction to Property Testing
20194161

Lecturers and Teaching Assistants

Dr. Reut Levi, Prof. Oded Goldreich
Orr Paradise

Course Schedule and Location

2019
First Semester
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

Comments

N/A

Prerequisites

No

Restrictions

50

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Pass / Fail

Grade Breakdown (in %)

100%
grade by assignment

Evaluation Type

Final assignment

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

2

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:
  1. Describe the key notions and principles of the area of property testing.
  2. Demonstrate familiarity with basic paradigms and techniques of the area of property testing.
  3. Apply notions, principles, paradigms, and techniques of property testing to their own research.
  4. 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

Website

N/A