Forschungsseminar Komplexität und Kryptografie


Forschungsseminar


Leitung: Prof. Johannes Köbler [HU] Das Forschungsseminar findet in der Rudower Chaussee 25 in Raum 4.007 statt.

Zugang zur Mailingliste für die Vortragsankündigungen


Termine und Themen
Termin	Person	Themen aus dem WS 2005/2006	Ort
25. Jan., 15:00 Uhr	Wolfgang Kössler	Schätzung von Binomialwahrscheinlichkeiten (Teil 2)	[RUD 25, 4.007]
18. Jan., 15:00 Uhr	Wolfgang Kössler	Schätzung von Binomialwahrscheinlichkeiten (Teil 1)	[RUD 25, 4.007]
14. Dez., 15:00 Uhr	Johannes Köbler	Komplexität von Isomorphieproblemen für Bäume und gefärbte Graphen (Teil 2)	[RUD 25, 4.007]
7. Dez., 15:00 Uhr	Johannes Köbler	Komplexität von Isomorphieproblemen für Bäume und gefärbte Graphen (Teil 1)	[RUD 25, 4.007]
30. Nov., 15:00 Uhr	Wolfgang Kössler	Vorstellung einiger statistischer Problemstellungen anhand von Beispielen	[RUD 25, 4.007]
23. Nov., 15:00 Uhr	Olaf Beyersdorff	Disjunkte Tupel von NP-Mengen (Teil 3)	[RUD 25, 4.007]
16. Nov., 14:15 Uhr	Olaf Beyersdorff	Disjunkte Tupel von NP-Mengen (Teil 2)	[RUD 25, 4.007]
9. Nov., 17:15 Uhr	Olaf Beyersdorff	Disjunkte Tupel von NP-Mengen (Teil 1)	[RUD 25, 4.112]
2. Nov., 17:00 Uhr	Johannes Köbler	PAC-Erlernbarkeit von k-Juntas	[RUD 25, 4.112]
26. Okt., 17:00 Uhr	Carsten Schwarz	Hyperelliptic Curve Cryptosystems	[RUD 25, 4.112]
12. Oktober	Berlin-Hannover-Jena-Seminar zur Komplexitätstheorie	1. Complexity Classes of Disjoint NP-pairs (Olaf Beyersdorff) 2. Generalized Modal Satisfiability (E. Hemaspaandra) 3. Die Komplexität hybrider Logiken über transitiven Rahmen (Thomas Schneider) 4. Parameterisierte Erlernbarkeit von k-Juntas (Johannes Köbler)	[Jena]
---------	---------	---------	---------
Termin	Person	Themen aus dem SS 2005	Ort
7. Juli	Olaf Beyersdorff	Disjoint NP-pairs from propositional proof systems (Teil 2)	[HU]
30. Juni	Olaf Beyersdorff	Disjoint NP-pairs from propositional proof systems	[HU]
23. Juni	Thomas Karbe	Optimal Flow Distribution Among Multiple Channels with Unknown Capacities	[TU]
9. Juni	Johannes Köbler	AKS-Algorithmus zur Entscheidung des Primzahlproblems in Polynomialzeit (Teil 3)	[HU]
2. Juni	Till Tantau	Untere Schranken fuer die Beschreibungskomplexitaet der Erreichbarkeit (Teil 2)	[TU]
19. Mai	Till Tantau	Untere Schranken fuer die Beschreibungskomplexitaet der Erreichbarkeit (Teil 1)	[TU]
12. Mai	Carsten Schwarz	Undeniable Signatures	[HU]
28. April	Johannes Köbler	AKS-Algorithmus zur Entscheidung des Primzahlproblems in Polynomialzeit (Teil 2)	[HU]
20. April	Johannes Köbler	AKS-Algorithmus zur Entscheidung des Primzahlproblems in Polynomialzeit	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem WS 2004/2005	Ort
22. Februar	Gemeinsames Forschungsseminar von: HU TU Uni Hannover		[TU]
9. Februar	Olaf Beyersdorff	Kanonische disjunkte NP-Paare	[HU]
2. Februar	Arfst Nickelsen	Überlegungen zu notwendigen und hinreichenden Bedingungen für die Existenz von One-Query-Reduktionsbeziehungen zwischen Teilinformationsklassen	[TU]
26. Januar	Falk Niehörster	Einführung in die Quanteninformatik und der Existenzbeweis einer universellen Quanten-Turingmaschine	[HU]
19. Januar	André Hernich	Charakterisierungen von P mittels Selbstreduktion und Teilinformation	[TU]
12. Januar	Matthias Schwan	Sicherheitsanforderungen und -massnahmen in Funknetzen (WLAN)	[HU]
15. Dezember	Birgit Schelm	Die Komplexität nichtmonotoner Logiken	[TU]
8. Dezember	Andre Hernich	Haplotypisierung mit unvollständigen Daten ist NP-vollständig	[TU]
3. Dezember	Gemeinsames Forschungsseminar von: HU TU Uni Hannover		[Hannover]
24. November	Johannes Köbler	SL=L	[HU]
10. November	Till Tantau	Die Komplexitaet des Findens von Wegen in Graphen mit beschraenkter Unabhaengigkeitszahl	[TU]
3. November	Carsten Schwarz	RSA-Based Undeniable Signatures	[HU]
27. Oktober	Lyuda Kotomina	Construction of the pseudorandom number generators that use fast machine instructions (addition and XOR) and analysis of there cryptographic characteristics	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem SS 2004	Ort
14. Juli	André Hernich	Zusammenfall von Turing- und Truth-table-Reduktionsabschluss für Sprachen aus P[NONSEL_n]	[TU]
7. Juli	Birgit Schelm	On the role of the class HP in separating average-case approximation classes	[TU]
30. Juni	Piyush P Kurur	On the complexity of computing the units of a number field	[HU]
9. Juni	Matthias Schwan	Vorstellung des Projekts "Verisoft - Beweisen als Ingenieurwissenschaft"	[HU]
2. Juni	Arfst Nickelsen	Selbstreduzierbare Sprachen in P[(2m-1)-SIZE_m] und in P[2-CARD_2] (leicht zwei-zählbare Sprachen)	[TU]
26. Mai	Lorenz Weizäcker	Aggregate mit Schranken bzgl. der Tiefe und der Komponentengroesse	[HU]
19. Mai	Arfst Nickelsen	Beweis des Kardinalitätssatzes von Kummer	[TU]
21. April	Andrey Bogdanov	Simple Homomorphism Verification Tool: Konzeption, theoretische Grundlagen, Beispiele	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem WS 2003/04	Ort
31. März	Gemeinsames Forschungsseminar von: HU TU Uni Hannover	Themen der Vorträge: 1. Frozen Variables und die Postschen Klassen 2. Conjunctive Query 3. Complexity of Perfect Phylogeny Haplotyping 4. HP != AvgP (Birgit Schelm)	[TU]
18. Februar	Carsten Schwarz	RSA-Based Undeniable Signatures	[HU]
11. Februar	Olivier Bouissou	co-NP enthalten in NP/1 gdw PH = D	[TU]
28. Januar	Johannes Köbler	Derandomisierung von BPP (Teil 2)	[HU]
21. Januar	Johannes Köbler	Derandomisierung von BPP (Teil 1)	[HU]
14. Januar	Olaf Beyersdorff	Starke Beweissysteme - implizite Beweise	[HU]
7. Januar	Arfst Nickelsen	Für leicht $2$-zählbare Sprachen fallen Turing- und Truth-Table-Abschluss zusammen.	[TU]
12. Dezember	Gemeinsames Forschungsseminar von: HU TU Uni Hannover	Themen der Vorträge: 1. Eine Charakterisierung von FPSPACE (Matthias Galota) 2. Erfüllbarkeitsprobleme (Heribert Vollmer) 3. Durchschnittskomplexität und Derandomisierung (Johannes Köbler)	[HU]
3. Dezember	Andrew Bogdanov	Statistische verdeckte Kanaele in Computernetzen	[HU]
26. November	Andrew Bogdanov	Statistische verdeckte Kanaele in Computernetzen	[HU]
19. November	Lionel Poeffel	Durchschnittskomplexitaet unter universellen Verteilungen	[TU]
12. November	Lionell Poeffel	Durchschnittskomplexitaet unter universellen Verteilungen	[TU]
5. November	Ben Bässler	Entwicklung und Analyse eines biometrischen Authentifikationsprotokolls Simple-Homomorphism-Verification-Tool	[HU]
29. Oktober	Ben Bässler	Entwicklung und Analyse eines biometrischen Authentifikationsprotokolls Simple-Homomorphism-Verification-Tool	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem SS 2003	Ort
16.Juli	Matthias Schwan	Das Sicherheitsmodell Zugriffmatrix	[TU]
09.Juli	Johannes Köbler	Average Case Komplexität von NP- und anderen Problemen (Teil 2)	[HU]
02.Juli	Johannes Köbler	Average Case Komplexität von NP- und anderen Problemen (Teil 1)	[HU]
25.Juli	Arfst Nickelsen	1-tt-Reduktionen zwischen Teilinformationsklassen (Teil 2)	[TU]
18.Juli	Arfst Nickelsen	1-tt-Reduktionen zwischen Teilinformationsklassen (Teil 1)	[TU]
11.Juli	Birgit Schelm	Strukturelle Eigenschaften von Average Case Approximationsklassen	[TU]
04.Juni	Lorenz Weizäcker	Aggregate mit beschränkter Tiefe	[HU]
21.Mai	Till Tantau	Logspace-Optimierungsprobleme und ihre Aproximierbarkeit (Teil2)	[TU]
14.Mai	Olaf Beyersdorff	Disjunkte NP-Paare, Reduktion zwischen disjunkten NP-Paaren und Beweissysteme (Teil2)	[HU]
07.Mai	Olaf Beyersdorff	Disjunkte NP-Paare, Reduktion zwischen disjunkten NP-Paaren und Beweissysteme (Teil1)	[HU]
30.April	Till Tantau	Logspace-Optimierungsprobleme und ihre Aproximierbarkeit (Teil1)	[TU]
23.April	Lorenz Weizäcker	Warum entscheiden polynomiell grosse Aggregate mit Komponentengrösse 1 alle Sprachen aus PSPACE?	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem WS 2002/03	Ort
26.Februar	Gemeinsames Forschungsseminar von: HU TU Uni Hannover	Themen der Vorträge: Tautologien aus Pseudozufallszahlgeneratoren (O. Beyersdorff) Vollständige Probleme für Average Case Approximationsklassen (B. Schelm) Die Komplexität von Constraint-Satisfaction-Problemen (Prof. H.Vollmer)	[TU]
05.Februar	Arfst Nickelsen	Membership comparable and p-selective Sets (R.Beigel, L.Fortnow, A.Pavan)	[TU]
29.Januar	Till Tantau	Anfragekomplexität von membership-vergleichbaren Sprachen	[TU]
22.Januar	Johannes Köbler	Einige Beweise zu: Die Komplexität des Erlernens von Konzeptklassen durch Fragen	[HU]
15.Januar	Johannes Köbler	Die Komplexität des Erlernens von Konzeptklassen durch Fragen	[HU]
18.Dezember	Till Tantau	Beweise zum Kreuzproduktsatz in der Logik	[TU]
11.Dezember	Till Tantau	Der Kreuzproduktsatz in der Logik	[TU]
04.Dezember	Matthias Schwan	Biometrische Identifikationssysteme	[HU]
27.November	Lorenz Weizäcker	Durch Schaltkreise mit Zyklen charakterisierte Sprachklassen	[HU]
13.November	Birgit Schelm	Vollständige Probleme für Average Case Komplexitätsklassen	[TU]
06.November	Olaf Beyersdorff	Theorie disjunkter NP-Paare (Fortsetzung)	[HU]
30.Oktober	Arfst Nickelsen	Primes in P (Beweis von Agrawal, Kayal und Saxena)	[TU]
23.Oktober	Olaf Beyersdorff	Theorie disjunkter NP-Paare	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem SS 2002	Ort
17.Juli	Till Tantau	Ein Beweis des Kardinalitätssatzes für endliche Automaten für zwei Worte	[TU]
12.Juli	Gemeinsames Forschungsseminar von: HU TU Uni Hannover	Themen der Vorträge: Vollständigkeitsresultate für Graphisomorphie (Prof. Köbler) Erlernbarkeit von DNF Formeln mittels statistischer Fragen (W. Lindner) Drei gute Gründe an die Kardinalitätsvermutung für endliche Automaten zu glauben (T. Tantau)	[TU]
03.Juli	Olaf Beyersdorff	Beschränkte Arithmetik und aussagenlogische Beweissysteme (Fortsetzung)	[HU]
26.Juni	Olaf Beyersdorff	Beschränkte Arithmetik und aussagenlogische Beweissysteme	[HU]
19.Juni	Birgit Schelm	Average Case Komplexität von Approximationsproblemen	[TU]
12.Juni	Wolfgang Lindner	Randomisiertes Erlernen boolescher Schaltkreise	[HU]
05.Juni	Arfst Nickelsen	Erreichbarkeit in Graphen mit beschränkter Unabhängigkeitszahl	[TU]
29.Mai	Norbert Herold	Firewalls und ihre Anwendung	[HU]
22.Mai	Arfst Nickelsen	Linearer Advice für Teilinformationsklassen	[TU]
15.Mai	Ben Bässler	Angriffe auf den AES	[HU]
08.Mai	Ben Bässler	Spezifikation des Advanced Encryption Standard. Kurz: AES	[HU]
24.April	Till Tantau	Computation with Absolutely No Overhead	[TU]
---------	---------	---------	---------
Termin	Person	Themen aus dem WS 2001/02	Ort
06.Februar	Arfst Nickelsen	Obere Schranken für die Broadcasting-Zeit bei dynamischen Kantenfehlern in l-zusammenhängenden Graphen	[TU]
30. Januar	Prof. Köbler	Optimale Beweissysteme und Promise-Klassen - Teil 2	[HU]
23. Januar	Prof. Köbler	Optimale Beweissysteme und Promise-Klassen - Teil 1	[HU]
16. Januar	Birgit Schelm	Wie nützlich sind Lösungen zu Approximationsproblemen als Orakel? - Teil 2	[TU]
19. Dezember	Birgit Schelm	Wie nützlich sind Lösungen zu Approximationsproblemen als Orakel? - Teil 1	[TU]
21. November	Till Tantau	On the Reducibility of Sets Inside NP sets with Low Information Content - Part II	[TU]
14. November	Till Tantau	On the Reducibility of Sets Inside NP sets with Low Information Content - Part I	[TU]
7. November	Olaf Beyersdorff	Fragmente der Peano-Arithmetik	[HU]
31. Oktober	Till Tantau	Reachability in Tournaments	[TU]
24. Oktober	Matthias Schwan	Die digitale Signatur heute	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem SS 2001	Ort
18. Juli	Prof. Köbler	GI mit beschränkter Farbklassengröße	[HU]
11. Juli	Arfst Nickelsen	Advice für polynomielle Teilinformationsklassen	[TU]
4. Juli	Olaf Beyersdorff	Über die Länge von Resolutionsbeweisen - eine spieltheoretische Variante des Beweises von Haken nach P. Pudlak	[HU]
27. Juni	Birgit Schelm	Theorie der Average Case Komplexität von Approximationsproblemen	[TU]
20. Juni	Matthias Schwan	Elliptische Kurven	[HU]
13. Juni	Till Tantau	Wie diagonalisiert man mittels endlicher Automaten?	[TU]
6. Juni	Wolfgang Lindner	Fixed-Parameter-Erlernbarkeit (3.ter Teil)	[HU]
23. Mai	Wolfgang Lindner	Fixed-Parameter-Erlernbarkeit (2.ter Teil)	[HU]
16. Mai	Arfst Nickelsen	Fixed Parameter Tractability	[TU]
9. Mai	Wolfgang Lindner	Fixed-Parameter-Erlernbarkeit (1.ter Teil)	[HU]
---------	---------	---------	---------
Termin	Person	Themen aus dem WS 2000/01	Ort
24. Januar	Till Tantau	Endliche Automaten und Verboseness	[TU]

Carsten Schwarz

Leitung: Prof. Johannes Köbler [HU]