Subjects

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

Computational Complexity - NTIN082

Title:	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 2016 to 2016
Semester:	winter
E-Credits:	3
Hours per week, examination:	winter 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
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 :	NTIN081

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 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ů.

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.

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