Group:Complexity Group
Title: Matrix Rigidity and Communication Complexity
Speaker: Jayalal Sarmaon Tsinghua University
Time: 2010-06-02 15:30-2010-06-02 17:00
Venue: FIT 1-222

Abstract:

This talk will focus around the following theorem due to Razborov: If there exists an explicit family of 0-1 matrices of high rigidity then there is a language outside the polynomial hierarchy in communication complexity. This appears in an unpublished manuscript (in Russian). Recently this result was reproved and improved using a different strategy by Wunderlich. In this talk I will introduce the basic structural communication complexity and present Wuderlich's proof about relating it to matrix rigidity. The paper is available here: http://www.eccc.uni-trier.de/report/2010/086/




Short Bio: