Tata Institute of Fundamental Research
The Log-Approximate-Rank Conjecture is False
STCS Seminar
Speaker:
Suhail Sherif
Organiser:
Ramprasad Saptharishi
Date:
Tuesday, 27 Nov 2018, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Suhail Sherif |
| Organiser: | Ramprasad Saptharishi |
| Date: | Tuesday, 27 Nov 2018, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).