Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

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.

Presseartikel