The log rank conjecture for modular communication complexity

DOI10.1007/PL00001612MaRDI QIDQ5957091zbMATH OpenOpenAlexWikidataFDO

Authors Christoph Meinel, Stephan Waack

Publication date 28 February 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00001612

zbMATH Keywords

log rank conjecturemodular communication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Boolean functions (06E30)

Recommendations

• The ``log rank conjecture for modular communication complexity
• On the ``log rank-conjecture in communication complexity
• On rank vs. communication complexity
• Recent advances on the log-rank conjecture in communication complexity
• En route to the log-rank conjecture: new reductions and equivalent formulations

Cited in

(10)

• On Toda’s Theorem in Structural Communication Complexity
• Lower bounds for the modular communication complexity of various graph accessibility problems
• The log-approximate-rank conjecture is false
• An additive combinatorics approach relating rank to communication complexity
• The ``log rank conjecture for modular communication complexity
• On the ``log rank-conjecture in communication complexity
• En route to the log-rank conjecture: new reductions and equivalent formulations
• The corruption bound, log-rank, and communication complexity
• Min-rank conjecture for log-depth circuits
• Recent advances on the log-rank conjecture in communication complexity

This page was built for publication: The log rank conjecture for modular communication complexity

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