The log-approximate-rank conjecture is false

DOI10.1145/3313276.3316353zbMath1433.68144OpenAlexW2950519576MaRDI QIDQ5212746

Suhail Sherif, Nikhil S. Mande, Arkadev Chattopadhyay

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

spectral normlog-rank conjectureparity decision treesrandomized communication complexityapproximate nonnegative rank

Mathematics Subject Classification ID

Randomized algorithms (68W20) Boolean functions (94D10) Communication complexity, information complexity (68Q11)

Related Items (4)

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A generalization of a theorem of Rothschild and van Lint

This page was built for publication: The log-approximate-rank conjecture is false