Nondeterministic communication complexity with help and graph functions

DOI10.1016/J.TCS.2019.02.026MaRDI QIDQ2420638zbMATH OpenOpenAlexWikidataFDO

Authors Adi Shraibman

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

communication complexitygraph functionsmulticolor discrepancynumber on the forehead model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We define nondeterministic communication complexity in the model of communication complexity with help of Babai, Hayes and Kimmel. We use it to prove logarithmic lower bounds on the NOF communication complexity of explicit graph functions, which are complementary to the bounds proved by Beame, David, Pitassi and Woelfel.

Recommendations

• scientific article; zbMATH DE number 1775457
• Communication Lower Bounds Via the Chromatic Number
• scientific article; zbMATH DE number 1256774
• Non-deterministic communication complexity with few witnesses
• The cost of the missing bit: Communication complexity with help

Cites work

• Communication Complexity
• scientific article; zbMATH DE number 5130813 (Why is no real title available?)
• Nearly complete graphs decomposable into large induced matchings and their applications
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• The cost of the missing bit: Communication complexity with help
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems

Cited in

(5)

• scientific article; zbMATH DE number 1256774 (Why is no real title available?)
• scientific article; zbMATH DE number 1775457 (Why is no real title available?)
• Communication Lower Bounds Via the Chromatic Number
• The cost of the missing bit: Communication complexity with help
• New bounds on the half-duplex communication complexity

This page was built for publication: Nondeterministic communication complexity with help and graph functions

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