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)
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
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
(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, email@example.com