Basic Information

Objective:

This course aims to introduce Boolean functions from a complexity theoretic view. The first part of the course will introduce the notion of complexity for Boolean functions with Boolean Circuits as a computational model. The primary focus will be structural aspects of Boolean circuits and lower bounds for various class of circuits. The second part of the course will expose the students to the notion of communication complexity of Boolean functions.

Syllabus:

Theme 1 : Circuit Complexity and Lower Bounds - Boolean Circuits, Basic circuit design and complexity classes. Decision trees, Branching Programs, Uniformity, Basic containments and Simulations - Parity is not in AC^0 - three different proofs, Monotone circuit lower bounds, Power of negations in circuits. Graph Complexity. Span Programs. A brief introduction to Proof Complexity.

Theme 2: Communication Complexity

Two party communication Complexity

Deterministic protocols. Rectangle Covers and rank. Lower bounds. Randomized Protocols. Private vs Public.

Multi-party communication Complexity

Number on the forehead model.

Applications

Circuits. Streaming. Data Structures. Extensional Complexity of Polytopes.

Evaluation:

Problem Sets: 45%
Project + Presentation: 40%
End Sem 15%
Project: The project involves study of a specific problem/area within Communication Complexity or Boolean Circuit Complexity. Rather than being concentrated towards the end of the semester, we plan to start the project in early February. We plan to have 4 interim meetings and a final oral presentation for the evaluation of the project.