Introduction to Boolean Function Complexity

Advanced Course, 2+1

Basic Information


Wednesday, 12:15 - 13:45, E1.4 024

Lecturer:Nitin Saurabh
First lecture:17.04.2019

Every other Friday 12:15 - 13:45,  E1.4 024

Assistant:Anurag Pandey
First tutorial:



There will be oral exams at the end of the semenster.

Mailing list:

Please register here:

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.


  • 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


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



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




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




Boolean Function Complexity - by Stasys Jukna