A short course on constant-depth boolean circuit lower bounds

CURS MÀSTER IN COMPUTING


Dates: from May 10h to 14th.
Hours: 15:00-17:30
Location: Campus Nord UPC, room S2 215, building Omega.

Title: A short course on constant-depth boolean circuit lower bounds


Speaker: Prof. Arkadev Chattopadhyay. University of Toronto


Summary:
Proving lower bounds on the amount of resources needed for computing functions in interesting and natural models of computation is a central endeavor in theoretical computer science.
One of the most natural models of computation is that of boolean circuits. Understanding the unrestricted model has proved to be very difficult.

A landmark result from the mid-eighties established that constant-depth circuits with boolean AND and OR gates cannot compute the parity function unless the size of the circuit is exponential. We will cover several different techniques of proving this classical rsult:

(i) Hastad's switching lemma, a purely combinatorial approach
(i) Razborov-Smolensky, using polynomials over finite fields
(ii)Aspnes-Beigel-Furst-Rudich using real polynomials
The latter two will lead us into two fundamental and fascinating model of computation, representing boolean functions as polynomials modulo a composite and as sign representations by real polynomials. understanding them, leads to natural and neat questions in mathematics that appear indispensable for making progress with circuits.

We will also intend to show Yao's upper bound on ACC (using Toda's idea) that leads to the communication complexity approach.

For PhD or Master students it is possible to get additional ECTS credits for this course, please contact Mercè Juan(merce@lsi.upc.edu) indicating your situation.
The course is organized under the mobility program for professors in University Master degrees funded by the Spanish Ministry of Education.