Property Testing
Advanced Course, 2+1
Basic Information
| Lectures: | Tuesday, 14:00 - 16:00, Zoom |
|---|---|
| Lecturer: | Themis Gouleakis |
| First lecture: | November 3rd |
| Tutorials: | Friday, 16:00-18:00, Zoom |
| Assistant: | Philip Wellnitz |
| First tutorial: | November 20th |
| Credits: | 5 |
| Exam: | |
| Prerequisites: | 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 (4pm) today (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]
Material
Course textbook: http://www.wisdom.weizmann.ac.il/~oded/PDF/pt-v3.pdf
Use of Zoom and privacy policy
We have decided to use Zoom (https://zoom.us/) as a videoconferencing service. Note that this provider (Zoom Video Communications, Inc., 55 Almaden Blvd, Suite 600, San Jose, CA 95113, USA) can access all data that you provide when registering for the video conference. If you do not provide personal data during the registration, there is still a possibility that Zoom identifies you using your IP address. We would not have decided to use Zoom if we considered this as a significant risk. Should you still have privacy concerns (and are not using an Internet Service Provider that cannot map IP addresses to your name), we suggest using an anonymization service such as Tor (https://www.torproject.org/).
We aim to create a pleasant lecture environment despite the current situation. Personal interactions on Zoom, with your microphone and camera switched on, may contribute to this environment. We also encourage you to ask questions verbally. Note that this is voluntary. You may switch off both your camera and your microphone, and register under a pseudonym. Questions are still possible, in particular using the chat function.
You can find Zoom's complete privacy policy at: https://zoom.us/de-de/privacy.html