Speaker: |
Suhail Sherif |

Organiser: |
Gunjan Kumar |

Date: |
Friday, 2 Nov 2018, 17:15 to 18:45 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In our recent work, "The Log-Approximate-Rank Conjecture is False", we show that randomized communication and approximate rank do not have the close relationship that we would have liked to believe, thus refuting the titular conjecture.

In this talk, we will discuss why communication and rank are believed to be related. We will also see that our counter-example actually stems from a poor understanding of the model of parity decision trees, leaving us with fundamental open problems even in such simple models of computation (joint work with Arkadev Chattopadhyay and Nikhil Mande).