School of Technology and Computer Science Seminars

Relating Communication Protocols and Polynomials

by Suhail Sherif (School of Technology and Computer Science, TIFR)

Friday, December 30, 2016 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.