SubjectsSubjects(version: 845)
Course, academic year 2019/2020
   Login via CAS
Computational Complexity - NTIN082
Title in English: Výpočetní složitost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. Mgr. Michal Koucký, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html