The Log-Approximate-Rank Conjecture Is False

DOI10.1145/3396695MaRDI QIDQ5133979zbMATH OpenOpenAlexWikidataFDO

Authors Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif

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

approximate nonnegative ranklog-rank conjectureparity decision treesrandomized communication complexityspectral norm

Mathematics Subject Classification ID

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

Recommendations

• The log-approximate-rank conjecture is false
• Around the log-rank conjecture
• En route to the log-rank conjecture: new reductions and equivalent formulations
• The log-rank conjecture and low degree polynomials
• scientific article; zbMATH DE number 1256713
• The linear-array conjecture in communication complexity is false
• On the ``log rank-conjecture in communication complexity
• Counterexamples to Okounkov’s log-concavity conjecture
• scientific article; zbMATH DE number 5666686
• scientific article; zbMATH DE number 653253

Cited in

(14)

• Upper bounds on communication in terms of approximate rank
• scientific article; zbMATH DE number 5666686 (Why is no real title available?)
• A short list of equalities induces large sign-rank
• The log-approximate-rank conjecture is false
• A generalization of a theorem of Rothschild and van Lint
• Around the log-rank conjecture
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Upper bounds on communication in terms of approximate rank
• One-way communication complexity of partial XOR functions
• Quantum and classical communication complexity of permutation-invariant functions
• On the communication complexity of finding a king in a tournament
• Tight bounds for the randomized and quantum communication complexities of equality with small error
• On parity decision trees for Fourier-sparse Boolean functions
• A lower bound on the trace norm of Boolean matrices and its applications

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5133979)