The Log-Approximate-Rank Conjecture Is False

DOI10.1145/3396695zbMath1491.68073OpenAlexW3036171685WikidataQ122897449 ScholiaQ122897449MaRDI QIDQ5133979

Suhail Sherif, Arkadev Chattopadhyay, Nikhil S. Mande

Publication date: 11 November 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3396695

zbMATH Keywords

spectral normlog-rank conjectureparity decision treesrandomized communication complexityapproximate nonnegative rank

Mathematics Subject Classification ID

Boolean functions (06E30) Randomized algorithms (68W20) Communication complexity, information complexity (68Q11)

Related Items (4)

A Short List of Equalities Induces Large Sign-Rank ⋮ Around the log-rank conjecture ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: The Log-Approximate-Rank Conjecture Is False