Tata Institute of Fundamental Research
Relating Communication Protocols and Polynomials
STCS Student Seminar
Speaker:
Suhail Sherif
Organiser:
Gowtham Raghunath Kurri
Date:
Friday, 30 Dec 2016, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Lee and Zhang showed that the communication complexity of "f composed with g" is high when f is hard to approximate with a low degree polynomial (also g has to be from a good class of functions, more details will be given in the talk). In this talk, we will look at a proof of this result by transforming a communication protocol for "f composed with g" into a polynomial for f.
| Speaker: | Suhail Sherif |
| Organiser: | Gowtham Raghunath Kurri |
| Date: | Friday, 30 Dec 2016, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Lee and Zhang showed that the communication complexity of "f composed with g" is high when f is hard to approximate with a low degree polynomial (also g has to be from a good class of functions, more details will be given in the talk). In this talk, we will look at a proof of this result by transforming a communication protocol for "f composed with g" into a polynomial for f.