Randomized communication versus partition number

DOI10.1145/3170711MaRDI QIDQ4973872zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3170711

zbMATH Keywords

partition numberrandomized communication

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 7204504
• Deterministic communication vs. partition number
• Partition Arguments in Multiparty Communication Complexity
• scientific article; zbMATH DE number 1263236
• Average and randomized communication complexity

Cited in

(18)

• Communication complexity with small advantage
• Partition Information and its Transmission Over Boolean Multi-Access Channels
• Randomised Broadcasting: Memory vs. Randomness
• Clique problem, cutting plane proofs and communication complexity
• Deterministic communication vs. partition number
• Rényi information complexity and an information theoretic characterization of the partition bound
• Low-sensitivity functions from unambiguous certificates
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• Query-to-communication lifting for BPP
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• scientific article; zbMATH DE number 7706048 (Why is no real title available?)
• The power of many samples in query complexity
• Randomized query composition and sabotage complexity
• Separations between combinatorial measures for transitive functions
• Randomized query composition and product distributions
• Quantum sabotage complexity
• Lifting to randomized parity decision trees
• Searching for falsified clause in random ( n)-CNFs is hard for randomized communication

This page was built for publication: Randomized communication versus partition number

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