[Mittagsseminar TI] Mittagsseminar am Donnerstag, 24. 4. 2025 (Bachelor-defense, in German)

[Günter Rote <rote@inf.fu-berlin.de>]

Sehr geehrte Damen und Herren,

hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel
„Removing popular faces with additional curves“ ein.

Betreuer/Erstgutachter: Prof. Günther Rote
Zweitgutachter: Prof. Wolfgang Mulzer

Die Verteidigung findet am Donnerstag, dem 24.04.2025, um 12 Uhr Mittag im
Raum SR055 in der Takustraße statt. Der Vortrag wird auf Deutsch gehalten.

Mit freundlichen Grüßen

Daniel Yu

Zusammenfassung:

In dieser Arbeit untersuchen wir das Problem, populäre Flächen mithilfe
des Hinzufügen von Kurven zu behandeln. De Nooijer, Terziadis, Weinberger,
Masárová, Mchedlidze, Löffler and Rote [1] haben gezeigt, dass dieses
Problem NP-schwer ist, sich jedoch unter bestimmten Parametern
randomisiert in polynomieller Zeit lösen lässt. Dieser Ansatz basiert auf
einer Reduktion auf das Problem, ob ein Polynom das Nullpolynom ist, wobei
die Entscheidung durch zufällige Auswertung des Polynoms über einem
geeigneten Körper getroffen wird.

Wir implementieren die Ideen und testen diesen Ansatz auf synthetisch
generierte Graphen. Unsere empirischen Auswertungen zeigen, dass die
Fehlerwahrscheinlichkeiten weit niedriger sind als die theoretischen
Obergrenzen und diese weiter minimiert werden können.

Gruß

Daniel
________________________

Dear all,

I hereby invite you to the defense of my bachelor's thesis with the title
"Removing popular faces with additional curves".

The defense will take place on Thursday, 24.04.2025 at 12:00 am in
Takustraße 9, seminar room 055.

The defense will be held in German.

First examiner & Supervisor: Prof. Günther Rote
Second examiner: Prof. Dr. Wolfgang Mulzer

Sincerely,

Daniel Yu

Abstract:

In this thesis we study the problem of resolving popular faces on curved
nonograms by adding curves to the arrangement. We implement the proposed
algorithm from Nooijer et al. [1], which uses a reduction to graphs and
polynomial identity testing. We also test the approach on automatic
generated nonogram puzzles and synthesized graphs. Further we added the
possibility of using more than one curve and give some empirical studies
on the runtime and error probability.

________________________

The preliminary slides can be found here:
https://docs.google.com/presentation/d/1iDqw8YQYFa1mi2nFouFdJ6xHt2EH5OLVij8xEayN_ow/edit?usp=sharing

Bibliography
[1] P. de Nooijer et al. “Removing Popular Faces in Curve Arrangements”.
Journal of Graph Algorithms and Applications 28.2 (Nov. 2024), pp. 47–82.
doi:10.7155/jgaa.v28i2.2988.