Boolean Function Complexity - NMAG457

• Title: Boolean Function Complexity
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2023
• 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: not taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: Navid Talebanfard
• Class: M Mgr. MSTR; M Mgr. MSTR > Volitelné

Annotation

English

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

The basic approach to the P vs. NP problem is through circuit complexity. Circuits provide a basic model for computing Boolean functions. We will show that several explicit functions cannot be computed by small circuits from various interesting restricted classes.

Literature

English

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

Stasys Jukna, Boolean Function Complexity, Advances and Frontiers, Springer, 2012.

Syllabus

English

Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (12.05.2022)

• De Morgan formulas, shrinkage under random restrictions

• Switching lemma, lower bound for the parity function

• Satisfiability coding lemma, depth-3 lower bounds

• Razborov-Smolensky, lower bounds for bounded depth circuits with modular gates