Seminar: Recent breakthroughs

• Course codes: B-AUK-S→ATTI-BS ·M-AuK-S→ATTI-MS
• External links: qis

Inhalt

Dieses Seminar bietet einen Einblick in das wissenschaftliche Arbeiten in der theoretischen Informatik und stellt eine hervorragende Möglichkeit dar, sich auf eine Bachelor/Master-Arbeit in diesem Gebiet vorzubereiten. Jede:r Teilnehmer:in sucht sich zu Beginn eine Publikation aus, die auf einer der international renommiertesten Konferenzen im Jahr 2020 oder 2021 erschienen ist oder dort noch erscheinen wird. Hierzu zählen STOC 2021, FOCS 2020 und SOSA 2020. Falls ein Titel Sie interessiert, finden Sie den Volltext des jeweiligen Papers in der Regel über eine Suche auf DBLP, Google Scholar, oder arxiv. Das Ziel Ihres Vortrag wird es sein, den anderen Studierenden die Grundlagen, die Problemstellung, die wichtigsten Ergebnisse, sowie Beweisideen zu vermitteln, die im Zusammenhang zur ausgewählten Arbeit stehen.

Vorraussetzungen

Freude an Algorithmen und Datenstrukturen sowie Mathematik sind wichtig. Vorwissen über Komplexitätstheorie und algorithmische Vertiefungsvorlesungen sind von Vorteil. Trotzdem werden Sie beim Lesen einer Publikation ganz viel zunächst nicht kennen oder verstehen. Das ist normal und geht mir auch so. Ein Ziel des Seminars ist es, dass Sie lernen, mit dieser Informationsflut umzugehen, und dann eigenständig Begriffe nachrecherchieren, die Sie noch nicht kennen.

Vorschläge

Sie sind frei in der Wahl des Papers, solange Sie nicht das selbe Paper wie jemand anders auswählen. Dennoch habe ich zur Inspiration hier ein paar der Paper zusammengestellt.

Wenn Sie im Bachelor sind, dies Ihr erstes Seminar ist, oder sich vor Theorie fürchten, und Sie sich ein besonders zugängliches Paper wünschen, können Sie sich beispielsweise eins dieser SOSA 2021 Paper aussuchen:

• One (more) line on the most Ancient Algorithm in History: In diesem sehr kurzen Paper geht es um eine neue Analyse des Euklidischen Algorithmus. Vermutlich ist es zu kurz für ein Seminarthema.
• On the Change-Making Problem: Effizienter Algorithmus, um mit Münzen passend zu bezahlen.

Ein (vermutlich schönes) Paper mit nicht ganz so vielen Vorraussetzungen:

• On a Decentralized (Δ+1)-Graph Coloring Algorithm

Wenn Sie ein anspruchsvolles Paper haben wollen, für das ich mich selbst besonders interessiere, empfehle ich eins der folgenden Themen:

• A full complexity dichotomy for immanant families
• Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
• Pseudodeterministic Algorithms and the Structure of Probabilistic Time
• 3.1n−o(n) Circuit Lower Bounds for Explicit Functions
• Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost
• Vertex Connectivity in Poly-logarithmic Max-flows
• Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution
• Strong Co-Nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly
• Robust testing of low dimensional functions
• Bipartite Perfect Matching as a Real Polynomial

Ziele

Sobald Sie eine Publikation als Thema ausgewählt haben, sollen Sie in der Vorbereitung zum Vortrag:

• lernen, wie man eine Forschungsarbeit liest,
• sich fehlende Grundbegriffe selbstständig anlesen,
• das wichtigste Ergebnis der Forschungsarbeit identifizieren,
• erarbeiten, was vor diesem Ergebnis der Stand der Forschung war, was in dieser Arbeit neu ist, und warum das Problem überhaupt interessant ist,
• das Thema in einer Art und Weise aufbereiten, die es den zuhörenden Studierenden erlaubt, die Problemstellung und das Ergebnis zu verstehen,
• in der Form einer verständlichen Beweisskizze im Vortrag begründen, warum das neue Ergebnis wahr ist.

Organisation

• Dieses Seminar bietet Platz für 12 theorieinteressierte Studierende.
• Die Vorbesprechung findet in Kalenderwoche 15 oder 16 statt, und dient hauptsächlich der Themenvergabe und Terminplanung.
• Lagebesprechungen finden in KW 17-23 statt, darin besprechen wir Ihren jeweiligen Stand informell. Sie bereiten also Fragen vor, zu den Grundlagen, der Literatur, oder dem Paper selbst. Sie berichten, wie weit Sie mit dem Thema vorangekommen sind, was Sie schon verstanden haben, und was Sie noch nicht verstehen. Ich hoffe, dass dieses Format allen Teilnehmern etwas bringt, ansonsten ändern wir das Format gerne wieder.
• Vorträge findet dann an 5 Terminen (vermutlich im Zeitraum KW 24-28) während des Semesters statt.

Formale Anforderungen

Um das Seminar zu bestehen, werden folgende Aktivitäten erwartet:

• Sie halten einen Vortrag von ca. 60-80 Minuten Länge über das gewählte Thema.
• Sie senden uns mindestens 7 Tage vor dem Vortrag einen Entwurf der Folien oder Ihres geplanten Tafelanschriebs zu. Sie erhalten dann Feedback zu Ihren Folien und zur Struktur Ihres Vortrags.
• Sie treffen sich mindestens einmal und mindestens 5 Tage vor dem Vortrag mit dem Professor oder einem Mitarbeiter, um den Vortrag zu besprechen. Dabei haben Sie Gelegenheit, Ihre inhaltlichen Fragen zum Thema zu stellen.

Bewertung

Nach dem Vortrag gibt es eine Feedbackrunde im Plenum. Die vorläufige Benotung erfolgt ebenfalls direkt nach dem Vortrag. Bewertet werden:

• Wie selbstständig lief die Vorbereitung ab? Selbstständig vorbereiten beinhaltet, dass Sie Verständnislücken aktiv identifizieren und im Voraus klären.
• Inwiefern haben Sie inhaltliche Fragen vor dem Vortrag geklärt?
• Wie haben Sie sich an die zeitliche Vorgabe gehalten?
• Wie effektiv haben Sie Fragen beantwortet?
• Wie intensiv haben Sie sich an Diskussionen beteiligt? (hierbei zählen sowohl aktive Fragen als auch hilfreiche Antworten)
• Wie gut haben Sie die Inhalte des Vortrags selbst durchdrungen?
• Wie nützlich waren die im Vortrag gezeigten Visualisierungen?
• Wie verständlich konnten Sie die Inhalte des Vortrags an die anderen Studierenden vermitteln?
• Wie unterhaltsam war Ihr Vortrag?
• Je kürzer oder einfacher das Paper ist, desto mehr Wert wird auf den Vortragsstil, das selbstständige Arbeiten, die Darstellung der umliegenden Literatur, und die Motivation gelegt (also z.B. warum ist das Paper interessant und auf welche Forschungsfragen hat das Ergebnis einen Einfluss?). Alternativ können Sie auch zwei kurze Paper bearbeiten.

Allgemeine Tipps

• Zeit für die Vorbereitung. Das Paper zu verstehen wird sehr viel Zeit in Anspruch nehmen. Fangen Sie so früh wie möglich an.
• Nicht verzweifeln. Es ist ganz natürlich, dass Sie die Hälfte der Begriffe, die in dem Paper vorkommen, nicht verstehen werden. Das geht mir oft genauso. Gehen Sie systematisch Begriff für Begriff vor, und klären Sie für jeden einzelnen Begriff, was er bedeutet. Schreiben Sie sich auf, was sie gelernt haben.
• Zeit für den Vortrag. Die vorgegebene Zeit von 60 Minuten geht viel schneller vorbei, als Sie zunächst denken. Ich rechne mit ca. 1-2 Minuten pro Folie.
• Stellen Sie Fragen. Nichts ist langweiliger, als ein Vortrag, bei dem Sie auf Folie 2 die Definition eines Hinzlipunzli nicht verstanden haben, weil der Vortragende darüber etwas zu schnell hinwegging. Übernehmen Sie Verantwortung und fragen Sie aktiv! Unwissenheit ist keine Peinlichkeit, sondern eine spannende Gelegenheit, etwas zu lernen.
• Seien Sie ehrlich. Es wird nicht erwartet, dass Sie alles wissen oder jede Frage beantworten können. Wenn Sie verwirrt sind, etwas nicht verstehen, oder einen Teil des Papers aus Zeitgründen nicht detailliert lesen konnten, stehen Sie dazu. Das ist wissenschaftliches Arbeiten.
• Seien Sie witzig. Bauen Sie einen Witz oder einen Spaß in den Vortrag ein (aber auf keinen Fall mehr als zwei Witze).
• Weniger ist mehr. Gehen Sie lieber bei wenigen Unterthemen in die Tiefe, als alles nur halbgar und halbverständlich anzureißen.