Informatik-Kolloquien
252. Informatik-Kolloquium
Öffentliche Verteidigung im Rahmen des Promotionsverfahrens
Herr Dipl.-Inf. Lutz Falke
TU Chemnitz
Fakultät für Informatik
Professur Theoretische Informatik
"Schwellwert für die Lösbarkeit von zufälligen Gleichungssystemen über Z3"
Mittwoch, 16.12.2015
16:30 Uhr, Straße der Nationen 62, 1/205
Alle interessierten Personen sind herzlich eingeladen!
Abstract 
Behandelt werden zufällige lineare Gleichungssysteme modulo 3, wobei in jeder Gleichung genau k Variablen vorkommen. Es wird gezeigt, dass der Schwellwert der Lösbarkeit solcher Gleichungsysteme bei der 2-Kern-Dichte von 1 liegt. Das Resultat ist eine Verallgemeinerung bereits bekannter Resultate für den modulo 2-Fall. Dabei entsteht der 2-Kern dadurch, dass wir alle Variablen mit nur einem Vorkommen löschen. Die Dichte ist definiert als der Quotient der Anzahl der Gleichungen durch die Anzahl der Variablen.
Im Rückblick ist dieses Resultat ein natürlicher Schwellwert und die Vermutung liegt nahe, dass er bei analogen Situationen über anderen Strukturen als Z3 auch gelten sollte. Allerdings sind schon im modulo 2 Fall die analytischen Probleme nicht gering, und der hier behandelte Fall braucht weitere analytische Einsichten.
Ein wesentlicher Punkt unseres Beweises ist die Verwendung eines komplexen Polynoms (hier ist r die primitive dritte Einheitswurzel)

.
Im modulo 2 Fall wurde an analoger Stelle das Polynom

gebraucht. Da

komplexe Koeffizienten enthält, ist es nicht von vornherein klar, ob eine Behandlung analog zum modulo 2 Fall möglich ist. Auch macht
die höhere Parameteranzahl die Sache komplizierter. Im Vergleich zum modulo 2 Fall, wo lokale Grenzwertsätze über gitterförmige Zufallsvariablen angewendet wurden, brauchen wir hier die Verallgemeinerung auf zweidimensionale gitterförmige Zufallsvektoren.