# Introduction to Boolean Function Complexity

## Basic Information

Lectures: Wednesday, 12:15 - 13:45, E1.4 024 Nitin Saurabh 17.04.2019 Every other Friday 12:15 - 13:45,  E1.4 024 Anurag Pandey 10.05.2019 5 There will be oral exams at the end of the semenster. Please register here: lists.mpi-inf.mpg.de/listinfo/bfc19 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.