Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Computational complexity and interactive protocols - NTIN081

Title:	Výpočetní složitost a interaktivni protokoly
Guaranteed by:	Computer Science Institute of Charles University (32-IUUK)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	not taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	prof. Mgr. Michal Koucký, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science
Co-requisite :	NTIN063

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KTI (26.04.2016)

This course extends the basic course on computational complexity (NTIN063). It covers hierarchy theorems for probabilistic computation, time-space trade-offs for SAT, Toda's Theorem, pseudo-random generators and interactive protocols.

Aim of the course - Czech

Last update: T_KTI (26.04.2016)

Naučit další látku z teorie složitosti: vztahy mezi třídami složitosti, pseudonáhodné generátory a interaktivni protokoly.

Course completion requirements -

Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

Oral exam.

Literature -

Last update: T_KTI (26.04.2016)

Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008.

Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008.

D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Computational Complexity, 16: 139-179, 2007.

D. van Melkebeek. Time-Space Lower Bounds for Satisfiability. Bulletin of EATCS, 73: 57-77, 2001.

Requirements to the exam -

Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.

Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.

Syllabus -

Last update: T_KTI (26.04.2016)

Nondeterministic time hierarchy and hierarchy for probabilistic computation

BPP and polynomial hierarchy

Time-space trade-off for SAT

Isolation Lemma and Toda's Theorem

Pseudo-random generators, Nisan's pseudo-random generator

Interactive protocols - Arthur-Merlin games (class AM, IP=PSPACE)

Multi-prover interactive protocols (MIP=NEXP)