Nonuniform computational models - NTIN082
Title: Neuniformní výpočetní modely
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
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: 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
Opinion survey results   Examination dates   SS schedule   Noticeboard   
Annotation -
Last update: T_KTI (26.04.2016)
This course extends the basic course on computational complexity (NTIN063). It covers various types of Boolean circuits and branching programs, their relationships and relationships to the usual complexity classes.
Aim of the course - Czech
Last update: T_KTI (26.04.2016)

Naučit další látku z teorie složitosti zejména v oblasti neuniformních výpočetních modelů.

Course completion requirements -
Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

The exam is oral.
Literature -
Last update: T_KTI (26.04.2016)

Stasys Jukna. Boolean Function Complexity: Advances and Frontiers.

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

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

Requirements to the exam -
Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

he 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)

Boolean circuits and P/poly

coNEXP is not in NEXP/poly

NP^NP does not have circuit of size O(n^k), for fixed k

Logarithmic depth circuit, Boolean formulas

Constant depth circuits

Parity not in AC0 - proofs of Razborov and Smolensky

Approximating MAJ in AC0

ACC0 vs CC0

Circuit depth reductions

Williams: NEXP is not in ACC0

Branching programs and their relationship to space bounded computation

Barrington's Theorem

Generalization of Barrington's Theorem for arithmetic formulas

Catalytic computation