Introduction to Boolean Function Complexity
Advanced Course, 2+1
Basic Information
| Lectures: | Wednesday, 12:15 - 13:45, E1.4 024 |
|---|---|
| Lecturer: | Nitin Saurabh |
| First lecture: | 17.04.2019 |
| Tutorials: | Every other Friday 12:15 - 13:45, E1.4 024 |
| Assistant: | Anurag Pandey |
| First tutorial: | 10.05.2019 |
| Credits: | 5 |
| Exam: | There will be oral exams at the end of the semenster. |
| Mailing list: | Please register here: lists.mpi-inf.mpg.de/listinfo/bfc19 |
| Prerequisites: | No prerequisites beyond basic familiarity with mathematical reasoning are required; prior knowledge on asymptotic notation and (occasionally) standard probabilistic notions will be useful for the course. |
Announcements
- 26.04.2019. Problem Set 1 has been sent to the mailing list. Due date: 6 May.
- 10.05.2019. Problem Set 2 has been sent to the mailing list. Due date: 20 May.
- 25.05.2019. Problem Set 3 has been sent to the mailing list. Due date: 3 June.
- 08.06.2019. Problem Set 4 has been sent to the mailing list. Due date: 17 June.
- 22.06.2019. Problem Set 5 has been sent to the mailing list. Due date: 1 July
Description
In this course, we study Boolean circuits as a model of computation. The object of our investigation will be Boolean functions. During the course we will see lower bounds against formulas, circuits, and bounded-depth circuits. We will also study decision trees and Fourier representation of Boolean functions.
The course material will be largely based on the book 'Boolean Function Complexity' by Stasys Jukna. In particular, we will loosely follow parts 1, 3, 4 and 5 in the book.
Tentaive list of topics:
1) De Morgan circuits and formulas
2) Gate elimination and formula lower bounds
3) Decision trees and Intro to Fourier analysis
4) Lower bounds against constant depth circuits
5) Time permiting: More applications of Fourier analysis
Schedule
Lectures
| Date | Topics | Notes |
| 17.04.2019 | De Morgan Circuits, Formulas, Uniformity, Riordan-Shannon's lower bounds | Lecture 1 |
| 24.04.2019 | Lupanov's upper bound, Gate elimination technique, Linear lower bounds against circuits | Lecture 2 |
| 01.05.2019 | Canceled due to holiday | |
| 08.05.2019 | Formula depth reduction, Khrapchenko's lower bound, Subbotovskaya's method of random restrictions | Lecture 3 |
| 15.05.2019 | Subbotovskaya's method (contd.), Shrinkage of formulas, Andreev's function, Neciporuk's method | Lecture 4 |
| 22.05.2019 | Decision tree complexity, Certificate complexity, P = NP ∩ coNP for decision tree depth, Sensitivity | Lecture 5 |
| 29.05.2019 | Room change (Room 22) | Block sensitivity, polynomial representation, degree | Lecture 6 |
| 05.06.2019 | Introduction to Fourier analysis, Lower bound for decision tree size | Lecture 7 |
| 12.06.2019 | Razborov - Smolensky's lower bound for constant depth circuits | Lecture 8 |
| 19.06.2019 | Hastad's Switching Lemma | Lecture 9 |
| 26.06.2019 | Switching Lemma continued, Lower bound for Parity, Intro to LMN theorem | Lecture 10 |
| 03.07.2019 | Canceled | |
| 10.07.2019 | Canceled | |
| 17.07.2019 | LMN Theorem and constant depth circuits | Lecture 11 |
Tutorials
| Date | ||
| 10.05.2019 | Problem Set 1 discussed. | |
| 24.05.2019 | Problem Set 2 discussed. | |
| 07.06.2019 | Problem Set 3 discussed. | |
| 21.06.2019 | Problem Set 4 discussed. | |
| 5.07.2019 | Canceled | |
| 19.07.2019 | Problem Set 5 discussed. |