19315401 Lecture

SoSe 16: Komplexitätstheorie

Wolfgang Mulzer

Comments

The first class takes place on Friday, 22.04.2016.

Contents

  • Complexity classes: P, NP, coNP, PH, L, SL, NL, coNL, PSPACE, NPSPACE, BPP, PP, ZPP, RP, #P, PARITY P, IP, AM, MA, EXP, NEXP, P/Poly, NC, ACC, BQP, PCP, MIP, etc. + oracles
  • Theorems: Cook-Levin, Time- and Space-hierarchy, Ladner, Mahaney, Savitch, Immerman-Szelepcsényi, Karp-Lipton, Adleman, Sipser-Gács, Valiant-Vazirani, Baker-Gill-Solovay, Goldreich-Levin, PCP, parallel repetition, Goldwasser-Sipser, Nisan-Wigderson, Razborov-Smolensky, Razborov-Rudich, sum-check protocol, Håstad's switching lemma, expander mixin lemma, leftover hashing lemma, etc.
  • Concepts: time, space, nondeterminism, advice, interaction, diagonalization, alternation, relativization, algebrization, naturalization, pseudo-randomness, error-correction, expander-graphs, discrete Fourier-analysis, etc.

Target Audience

M.S.-sutdents in Competer Science, Mathematics or similar courses of study. Afterwards, you can obtain a topic for a Master thesis.

Recommended Background 

Basic knowledge in Mathematics and Theoretical Computer Science: discrete Mathemtics, discrete probability theory, linear algebra, simple algebra and number theory, theory of algorithms, NP-completeness theory. More concretely: Contents of Mathematics for Computer Science, Theory of Computation, Algorithms and Data Structures, Advanced Algorithms

Website

http://www.inf.fu-berlin.de/lehre/SS16/CCT/

close

Suggested reading

  • S. Arora und B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  • O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
  • C. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
  • M. Sipser. Introduction to the Theory of Computation. Thomson Press, 2005.
  • I. Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer Verlag, 2003.
close

26 Class schedule

Regular appointments

Fri, 2016-04-22 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-04-29 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-05-06 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-05-13 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-05-20 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-05-27 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-06-03 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-06-10 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-06-17 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-06-24 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-07-01 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-07-08 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-07-15 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Fri, 2016-07-22 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Mon, 2016-04-25 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-05-02 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-05-09 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-05-23 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-05-30 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-06-06 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-06-13 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-06-20 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-06-27 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-07-04 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-07-11 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Mon, 2016-07-18 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer

Location:
T9/SR 005 Übungsraum (Takustr. 9)

Subjects A - Z