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.

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.2019  
29.05.2019Room change (Room 22) 
05.06.2019  
12.06.2019  
14.06.2019  
19.06.2019Cancelled (and added an extra lecture on 14 June. Time and Venue remains the same.) 
26.06.2019  
03.07.2019  
10.07.2019  
17.07.2019  

 

 

Tutorials

Date  
10.05.2019Problem Set 1 discussed. 
24.05.2019  
07.06.2019  
21.06.2019Cancelled (and added an extra tutorial on 28 June. Time and Venue remains the same.) 
28.06.2019  
5.07.2019  
19.07.2019  

 

 

Material

Boolean Function Complexity - by Stasys Jukna