discipline

Pure Math

subject

Complexity seminar

lecturers

Zoltán Király, Vince Grolmusz

credits

2

period

4

curriculum

Applications of the diagonalization method. Alternating hierarchy. Lower bounds for Boolean networks Turing machines with an oracle. Polynomial hierarchy. PSPACE-completeness. IP=PSPACE, MIP=NEXP, applications.

literature

Proceedings of the ACM STOC conferences and IEEE FOCS conferences.

Form of tuition

Lectures

mode of assessment

oral exam