Computation Over the Noisy Broadcast Channel with Malicious Parties
summary
Shows a protocol that computes bit‑exchange over a noisy broadcast channel tolerating up to half malicious parties while cutting per‑player communication from Θ(log N) to about Θ(√log N) (total ≈ N√log N). It preserves efficiency and simple decoding (property-preserving interactive coding), delays local majority guesses, then boosts consistency using locality-sensitive error‑correcting codes built from random linear combinations. Key claims: polynomial‑time parties, root‑log rounds, and robustness against mixed malicious broadcast strategies.
AI-written summary · about
chapters (4)
- 0:00Start
- 19:19Our Approach: Boost Before Guess
- 21:19Locality Sensitive Error Correcting Codes - Definition
- 23:35Locality Sensitive Error Correcting Codes - Construction
related talks
31mBroadcast Optimal Multi-Party Computation
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
32mNew Techniques for Building Information-Theoretic Asynchronous MPC with Linear Communication
57mCoding for Interactive Communication
33mError Correction for Streaming Messages
34mCapacity Inversion and MPC over Elastic Noisy Channels
46mTiming Matters: Online Dynamics in Broadcast Games
01h 03mClosing Keynote Day 2