Year: 2016 | |

11/14 | [elc] ELC C01 Seminar (Professor T. Pitassi) |

Place : CELC Seminar Room | |

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 |

horiyama@al.ics.saitama-u.ac.jp