Approximate Log Rank ConjectureSpeaker: Santoshini
Title: Approximate Log Rank Conjecture
Date: 29 Jul 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 323
Audience background: Basic linear algebra and probability theory
Abstract: In this talk, I present the not-so-recent breakthrough result of Arkadev, Nikhil and Suhail which was published in STOC 2019. The Log-Rank conjecture (LRC), introduced by Lovasz and Slaks in 1988, is a very simply-stated and fundamental conjecture on deterministic communication. Despite receiving intense research focus for the past three decades, this problem has not been resolved to a satisfying extent. The Log-Approximate-Rank conjecture (LARC) was defined by Lee and Shraibman in 2009 as a very natural analogue of the LRC for randomized communication. In this paper, the authors prove that the LARC is false! As an interesting application, the same kind of techniques were later used in a follow up paper by Anshu et al. to disprove the analogue of the same conjecture in the quantum world!