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 complexitynumber on the forehead modelgraph functionsmulticolor discrepancy

Mathematics Subject Classification ID

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

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

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

Cited in

(4)

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

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)