Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOG APPROXIMATE RANK:
Reports tagged with log approximate rank:
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