Tight bounds for communication-assisted agreement distillation

DOI10.4230/LIPICS.CCC.2016.6MaRDI QIDQ5368740zbMATH OpenOpenAlexFDO

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

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)

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

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)