School of Technology and Computer Science Seminars
The Log-Approximate-Rank Conjecture is False
by Suhail Sherif (STCS, TIFR)
Tuesday, November 27, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
Abstract: The Log-Approximate-Rank Conjecture was a long-standing conjecture which posited that the randomised communication complexity of a function and log of the approximate rank of its communication matrix are polynomially related. In this work, we introduce a function F that refutes this conjecture. We will discuss a drawback of rank-like measures and see a proof that F has small approximate rank, yet is hard for randomised communication (joint work with Arkadev Chattopadhyay and Nikhil Mande). |
Organised by | Ramprasad Saptharishi |