# Property Testing

## Basic Information

Lectures: Tuesday, 14:00 - 16:00, Zoom Themis Gouleakis November 3rd Friday, 16:00-18:00, Zoom Philip Wellnitz November 20th 5 Knowledge of basic probability theory (e.g http://www.wisdom.weizmann.ac.il/~oded/PDF/pt-apdx.pdf) and randomized algorithms.

## Announcements

• There will be a regular lecture in the tutorial time slot (4pmtoday (2020-11-13). The zoom link will be announced on the mailing list.
• No lecture today (2020-11-10), please fill out this poll: https://dudle.inf.tu-dresden.de/proptest-tut/ for an alternative slot for this week's lecture. (Starting from next week, the chosen slot will also be the slot for the tutorials.)
• Please register to the course mailing list: https://lists.mpi-inf.mpg.de/listinfo/proptest21

## Description

This course offers a graduate introduction to property testing, which studies how to detect structural properties of huge objects by only examining a sub-linear fraction of these objects at random. The goal is to determine if the object has the aforementioned property or is “far” from every object that has the property. The study of such sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms.

Some topics: Testing for properties of graphs (triangle freeness, bipartiteness, etc); Testing for properties of distributions ( uniformity/identity, independence, monotonicity, is it a sum of independent variables?); Testing properties of functions (linearity, monotonicity, etc).

## Schedule (lectures)

03.11: Introduction and Motivation (Example: Majority property) [video] [notes]

13.11: Definitions and examples (sortedness testing) [video] [notes]

17.11: Linearity testing [video] [notes]

24.11: Testing monotonicity of functions [video] [notes]

01.12: Testing dictatorship and k-juntas [video] [notes]

08.12: Lower bound techniques [video] [notes]

15.12: Introduction to graph property testing [video] [notes]

22:12: (Christmas break)

29:12: (Christmas break)

05.01: Graph property testing: Testing triangle-freeness [video] [notes]

12.01: Graph property testing: Testing bipartiteness (upper bound and lower bound) [video] [notes]

19.01: Testing Distributions [video] [notes]

26.01: Distribution Identity testing [video] [notes]

02.02: Special topics in distribution testing [video] [notes]