TKS-Seminar

Seminar im WS 2010/11

Gehalten von Prof. Dr. Nicole Schweikardt

Aktuelles

• Der erste Termin des TKS-Seminars im Wintersemester ist am Mittwoch, 20.10.2010, 16:15 Uhr.

Einführung

Das TKS-Seminar richtet sich an Mitglieder der Arbeitsgruppe Theorie komplexer Systeme sowie an alle, die Interesse an theoretischer Informatik haben.
Kreditpunkte oder ein Seminarschein können hier nicht erworben werden — dafür aber vertiefte Kenntnisse in theoretischer Informatik, insbesondere in den Bereichen Logik, Komplexitätstheorie und Datenbanktheorie.

Im WS 10/11 werden wir das TKS-Seminar einerseits für Vorträge zu aktuellen Forschungsthemen der Arbeitsgruppe nutzen und andererseits weitere Teile der folgenden Bücher durcharbeiten:

• Noga Alon und Joel H. Spencer: The Probabilistic Method [AS] Wiley and Sons, 3. Auflage, 2008
• Martin Aigner und Günter M. Ziegler: Das BUCH der Beweise [AZ] Springer-Verlag, 3. Auflage, 2010

Das Seminar findet während der Vorlesungszeit des WS 10/11 i.d.R. Mittwochs von 16-18 Uhr in Raum 117 (Robert-Mayer-Str. 11-15) statt.

Termine

Mi, 20.10.2010, 16:15-17:45	Nicole Schweikardt Zur Lokalität von Arithmetik-invarianten FO-Anfragen (Teil 1)
Mi, 27.10.2010, 16:15-17:00	Nicole Schweikardt Zur Lokalität von Arithmetik-invarianten FO-Anfragen (Teil 2)
Mi, 03.11.2010, 14:00-15:45	Philipp Krause Optimal register allocation in polynomial time (Vortrag im Forschungsseminar Informatik und Mathematik, Raum SR 307)
Mi, 10.11.2010, 14:00-15:45	Siamak Tazari Lower Bounds for the Complexity of Monadic Second-Order Logic (Vortrag im Forschungsseminar Informatik und Mathematik, Raum AfE 102a)
Mi, 08.12.2010, 16:15-17:45	Morteza Monemizadeh Lovasz's Local Lemma — a non-constructive proof (siehe Kapitel 5 im Buch "The Probabilistic Method" von Alon und Spencer)
Mi, 22.12.2010, 16:15-17:00	Dominik D. Freydenberger A lower bound technique for the size of nondeterministic finite automata (Glaister, Shallit, IPL vol 59, pp. 75-77, 1996)
Mi, 12.01.2011, 12:30-14:00	Morteza Monemizadeh Lovasz's Local Lemma — a constructive proof (STOC'09-Arbeit von Robin A. Moser; J.ACM 2010 Arbeit von Robin A. Moser und Gabor Tardos)
Mi, 26.01.2011, 16:15-17:45	Joachim Bremer Inklusionsprobleme für nichtlöschende Patternsprachen
Mi, 09.02.2011, 14:15-15:45	Morteza Monemizadeh Lovasz's Local Lemma — a constructive proof: part II (STOC'09-Arbeit von Robin A. Moser; J.ACM 2010 Arbeit von Robin A. Moser und Gabor Tardos)
Mi, 23.02.2011, 14:15-15:45	Morteza Monemizadeh Lovasz's Local Lemma — applications (The Santa Clause Problem, General Ramsey-Type Graphs, Max-k-SAT)