WiSe 2014/2015 » Nonuniform Complexity and P-vs-NP
Ziegler

Aktuelles

14.01.2015	Der zweite Seminarblock findet statt am 23.1. (Freitag) ab 11h40 im S1/03-121, ab 13h30 im S2/15-201
11.11.2014	Der erste Seminarblock findet statt am 5.12. (Freitag) ab 11h40 im S1/03-116, ab 13h30 im S2/15-201
06.10.2014	Vorbesprechung 20.10.2014 um 16h im S2/02-A126

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin
Rösnick, Carsten	S2|15 228	4181

 

Literatur

• Bürgisser, Clausen, Shokrollahi: "Algebraic Complexity Theory" (HeBIS, Buch Habel, Amazon)

 

Content

P-versus-NP is arguably the most famous problem in Theoretical Computer Science.
Our recent lecture has explored algebraic approaches to lower complexity bounds that one might hope could some day prove P different from NP. However these arguments apply also to non-uniform algorithms: a separate one A_n for each input size n.

The present seminar, held (possibly in German) jointly with PD Dr. Ulrike Brandt from the Department of Computer Science and Dr. Carsten Rösnick, focuses on the power of such non-uniform algorithms.

Participants (picture):

• Johannes Buck
• Bastian Dörig
• Sven Jacob
• Joel Koschier
• Jan Kuske
• Raffael Link
• Giang Nam Nguyen
• Tobias Reinhard
• Moritz von Spankeren

 

Impressum | Datenschutzerklärung