Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NARESH BODDU:
All reports by Author Naresh Boddu:

TR18-201 | 30th November 2018
Anurag Anshu, Naresh Boddu, Dave Touchette

Quantum Log-Approximate-Rank Conjecture is also False

Comments: 1

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function $f$, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication ... more >>>




ISSN 1433-8092 | Imprint