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

DateTopicsNotes
17.04.2019De Morgan Circuits, Formulas, Uniformity, Riordan-Shannon's lower boundsLecture 1
24.04.2019Lupanov's upper bound, Gate elimination technique, Linear lower bounds against circuitsLecture 2
01.05.2019Canceled due to holiday 
08.05.2019Formula depth reduction, Khrapchenko's lower bound, Subbotovskaya's method of random restrictionsLecture 3
15.05.2019Subbotovskaya's method (contd.), Shrinkage of formulas, Andreev's function, Neciporuk's methodLecture 4
22.05.2019Decision tree complexity, Certificate complexity, P = NP ∩ coNP for decision tree depth, SensitivityLecture 5
29.05.2019Room change (Room 22) | Block sensitivity, polynomial representation, degreeLecture 6
05.06.2019Introduction to Fourier analysis, Lower bound for decision tree sizeLecture 7
12.06.2019Razborov - Smolensky's lower bound for constant depth circuitsLecture 8
19.06.2019Hastad's Switching LemmaLecture 9
26.06.2019Switching Lemma continued, Lower bound for Parity, Intro to LMN theoremLecture 10
03.07.2019Canceled 
10.07.2019Canceled 
17.07.2019  

 

 

Tutorials

Date  
10.05.2019Problem Set 1 discussed. 
24.05.2019Problem Set 2 discussed. 
07.06.2019Problem Set 3 discussed. 
21.06.2019Problem Set 4 discussed. 
5.07.2019  
19.07.2019  

 

 

Material

Boolean Function Complexity - by Stasys Jukna