Recent advances on the log-rank conjecture in communication complexity

zbMath1409.68118arXiv1403.8106MaRDI QIDQ4967160

Shachar Lovett

Publication date: 3 July 2019

Full work available at URL: https://arxiv.org/abs/1403.8106

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Deterministic Communication vs. Partition Number ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ On the binary and Boolean rank of regular matrices ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes