讨论组:复杂性研究组
标题:Matrix Rigidity and Communication Complexity
演讲人: Jayalal Sarmaon Tsinghua University
时间: 2010-06-02 15:30-2010-06-02 17:00
地点:FIT 1-222

内容:

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/




人物介绍: