# Course Identification

Introduction to Property Testing
20194161

## Lecturers and Teaching Assistants

Dr. Reut Levi, Prof. Oded Goldreich

## 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

N/A

No

50

English

## Attendance and participation

Expected and Recommended

Pass / Fail

100%

Final assignment

N/A
N/A
-
N/A

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.