ELC C01 Seminar

Date: November 14th, 2016, 15:00-16:00
Place: Center for ELC Seminar Room, Tokyo Tech. Tamachi CIC 4F

Title: The Amazing Power of Composition
Speaker: Toniann Pitassi (Unv. of Toronto)

Abstract:
In the last 10 years, hardness escalation theorems have proven to be
very powerful in communication complexity. Such theorems start with
a base function that is "lifted" via function composition
in order to get a new function whose communication complexity
is essentially the same as the much simpler query complexity of the
base function.
Simulation theorems, while often very difficult to prove,
have led to the resolution of many open problems in complexity theory.
In this talk, we will survey recent simulation theorems
for a variety of query complexity/communication complexity models.
We will show how they, in turn, resolve several longstanding open
problems including:

(1) The resolution of the partition number versus communication complexity;
(2) The resolution of Yannakakis' famous Clique versus Independent Set
    problem from 1988, and the Alon-Saks-Seymour conjecture in graph theory.
(3) The best known lower bounds for the famous log-rank conjecture of
    Lovasz and Saks (FOCS 1988), and 
(4) Optimal lower bounds for monotone formula size


Host: Osamu Watanabe, watanabe@is.titech.ac.jp