Round elimination in exact communication complexity

DOI10.4230/LIPICS.TQC.2015.206MaRDI QIDQ5278031zbMATH OpenFDO

Authors Jop Briët, Harry Buhrman, Teresa Piovesan, Florian Speelman, Debbie Leung

Publication date 12 July 2017

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

zbMATH Keywords

chromatic numberscommunication complexityprotocolsquantum communicationround elimination

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Nonselfadjoint operator theory in quantum theory including creation and destruction operators (81Q12)

Recommendations

• scientific article; zbMATH DE number 1954386
• Communication Lower Bounds Via the Chromatic Number
• New bounds on the classical and quantum communication complexity of some graph properties
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• Exponential separation of quantum and classical communication complexity

Cited in

(9)

• Topological bounds on the dimension of orthogonal representations of graphs
• Rounds in Communication Complexity Revisited
• Approximating the orthogonality dimension of graphs and hypergraphs
• Approximating the orthogonality dimension of graphs and hypergraphs
• Kernelization for orthogonality dimension
• Toward better depth lower bounds: a KRW-like theorem for strong composition
• On the quantum chromatic numbers of small graphs
• Kernelization for orthogonality dimension
• New hardness results for low-rank matrix completion

This page was built for publication: Round elimination in exact communication complexity

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