Tight bounds for communication-assisted agreement distillation

DOI10.4230/LIPICS.CCC.2016.6zbMATH Open1380.94067OpenAlexW2465286492MaRDI QIDQ5368740FDOQ5368740

Authors: Venkatesan Guruswami, Jaikumar Radhakrishnan 

Publication date: 10 October 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.6

Recommendations

• scientific article; zbMATH DE number 6297761
• Sublinear message bounds for randomized agreement
• The Communication Complexity of Distributed epsilon-Approximations
• Sample complexity bounds on differentially private learning via communication complexity
• Learning Theory
• A practical protocol for advantage distillation and information reconciliation
• Consistency in models for distributed learning under communication constraints
• On multiparty communication with large versus unbounded error
• Consensus on \(p\)-belief communication
• Consensus on \(p\)-belief communication

zbMATH Keywords

lower boundsinformation theorypseudorandomnesscommunication complexitycovering codeshypercontractivity

Mathematics Subject Classification ID

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

Cited In (2)

• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• One-message secure reductions: on the cost of converting correlations

This page was built for publication: Tight bounds for communication-assisted agreement distillation

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