En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations

DOI10.1007/978-3-662-43948-7_43zbMath1412.68064OpenAlexW151690135MaRDI QIDQ5167769

Dmitry Gavinsky, Shachar Lovett

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-43948-7_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (9)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ The landscape of communication complexity classes ⋮ On public-coin zero-error randomized communication complexity ⋮ Around the log-rank conjecture ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations