Zum Inhalt springenZur Suche springen

Master-Seminar: Property Testing


The first session will be on Tuesday, 5 April, 10:30 am in seminar room 25.12.O2.33.


Materials and further information will be provided via ILIAS.


Dr. Anja Rey


5 LP


  • Seminar  Tue 10:30 Uhr - 12:00 Uhr in 25.12.O2.33
  • a detailed time table will be announced soon


We study algorithmic techniques that allow us to solve relaxed decision problems efficiently such as testing whether a sparse graph is connected or „far away“ from being connected in sublinear time. Individual topics can include state of the art research in this area.

Learning Goals

  • to extract significant contents of a given topic and to reproduce them in a written and oral form
  • to evaluate the readability and technical quality of other abstracts
  • to plan and hold a presentation
  • to ask and answer adequate questions and to give and take constructuctive feedback


  • Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017

  • further literature will be announced in the beginning of the seminar according to the individual topics


  • Wahlpflichtbereich Theoretische Informatik
  • Schwerpunktbereich
  • Individuelle Ergänzung
  • Anwendungsfach für den Ergänzungsbereich im Master-Studiengang Mathematik
  • Wahlbereich im Master-Studiengang Artificial Intelligence and Data Science


Bachelor studierends can take part under the Voraussetzungen für den Vorgriff auf Mastermodule.

Knowledge from the following courses would be helpful:
 - Advanced Algorithms or Algorithmen und Datenstrukturen
 - Theoretische Informatik
 - wissenschaftliches Arbeiten.

During the seminar you will
 - write an abstract about a given topic
 - provide feedback via a peer review
 - present your topic
 - ask and answer questions
to gain 5 LP.