[iasmath-semru] Update: speaker changed. Theoretical Computer Science/Discrete Math Seminars -- Week of September 25, 2017

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of September 25, 2017

Update: Next week's speaker has changed. Avi Wigderson will speak on October 3.

--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------

Tuesday, September 26

Computer Science/Discrete Mathematics Seminar II
Topic: 		Lifting theorems in communication complexity and applications
Speaker: 	Toniann Pitassi, University of Toronto; Visiting Professor, School of Mathematics
Time/Room: 	10:30am - 12:30pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=129004

1 Lifting theorems in communication complexity and applications
    Toniann Pitassi

Communication complexity studies the minimal amount of information two 
parties need to exchange to compute a joint function of their inputs. 
Results, especially lower bounds in this basic model found applications 
in many other areas of computer science.

Lifting is a technique for proving lower bounds and separation results 
in communication complexity. A typical lifting theorem shows how a lower 
bound on the ``query complexity'' of a function (usually, a far simpler 
task) can be used to obtain a communication lower bound on a related 
function. Proofs of lifting theorems require interesting combinations of 
analytic, information theoretic and combinatorial techniques, and are 
applicable to a variety of communication models, and beyond.

In the first hour we will give a tutorial on several influential lifting 
theorems that have been proven in the last 5-10 years, and show how they 
have directly led to the resolution of many open problems in 
communication complexity, circuit complexity (including extension 
complexity) and proof complexity. Time permitting, I will discuss two 
new lifting theorems in the second hour. The first lifts randomized 
decision tree complexity to randomized communication complexity (joint 
work with Mika Goos and Thomas Watson) and the second one lifts 
Nullstellensatz complexity to a rank measure that captures monotone span 
programs (joint work with Robert Robere).

No special background will be assumed.

http://www.math.ias.edu/seminars/abstract?event=129004

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu