The cost of the missing bit: Communication complexity with help

DOI10.1007/S004930100009MaRDI QIDQ700359zbMATH OpenOpenAlexFDO

Authors László Babai, Thomas P. Hayes, Peter G. Kimmel

Publication date 20 October 2002

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930100009

zbMATH Keywords

communication complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Recommendations

• scientific article; zbMATH DE number 1775457
• The value of help bits in randomized and average-case complexity
• Nondeterministic communication complexity with help and graph functions
• The communication complexity of addition
• The communication complexity of addition
• Communication complexity with defective randomness
• On the complexity of communication complexity
• STACS 2004
• Non-deterministic communication complexity with few witnesses
• The cost of fault tolerance in multi-party communication complexity

Cited in

(11)

• One-way multiparty communication lower bound for pointer jumping with applications
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)
• The value of help bits in randomized and average-case complexity
• Nondeterministic communication complexity with help and graph functions
• On the communication complexity of high-dimensional permutations
• The function-inversion problem: barriers and opportunities
• Improved bounds and schemes for the declustering problem
• Communication lower bounds using directional derivatives
• Optimal collapsing protocol for multiparty pointer jumping
• scientific article; zbMATH DE number 1775457 (Why is no real title available?)
• The multiparty communication complexity of set disjointness

This page was built for publication: The cost of the missing bit: Communication complexity with help

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