The cost of the missing bit: Communication complexity with help

DOI10.1007/S004930100009zbMATH Open0996.68057OpenAlexW2611355853MaRDI QIDQ700359FDOQ700359

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

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)

Cited In (9)

• One-way multiparty communication lower bound for pointer jumping with applications
• Title not available (Why is that?)
• The value of help bits in randomized and average-case complexity
• Nondeterministic communication complexity with help and graph functions
• 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
• The multiparty communication complexity of set disjointness

Recommendations

• Non-deterministic communication complexity with few witnesses 👍 👎
• The communication complexity of addition 👍 👎
• The communication complexity of addition 👍 👎
• The value of help bits in randomized and average-case complexity 👍 👎
• Nondeterministic communication complexity with help and graph functions 👍 👎
• The cost of fault tolerance in multi-party communication complexity 👍 👎
• On the complexity of communication complexity 👍 👎
• STACS 2004 👍 👎
• Communication complexity with defective randomness 👍 👎
• Title not available (Why is that?) 👍 👎

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)