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 (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]

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