Fast interactive coding against adversarial noise

DOI10.1145/2661628MaRDI QIDQ5501938zbMATH OpenOpenAlexFDO

Authors Zvika Brakerski, Yael Tauman Kalai, Moni Naor

Publication date 14 August 2015

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

interactive coding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Coding theorems (Shannon theory) (94A24)

Recommendations

• Fast algorithms for interactive coding
• Coding for interactive communication
• Interactive Coding for Interactive Proofs
• Towards coding for maximum errors in interactive communication
• Towards optimal deterministic coding for interactive communication

Cites work

• A Mathematical Theory of Communication
• A sample of samplers: a computational perspective on sampling
• Checking the correctness of memories
• Class of constructive asymptotically good algebraic codes
• Codes for Interactive Authentication
• Coding for interactive communication
• Deterministic coding for interactive communication
• Efficient and Explicit Coding for Interactive Communication
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• scientific article; zbMATH DE number 1256711 (Why is no real title available?)
• scientific article; zbMATH DE number 1263215 (Why is no real title available?)
• scientific article; zbMATH DE number 1406782 (Why is no real title available?)
• Interactive channel capacity
• Linear-time encodable and decodable error-correcting codes
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• Optimal error rates for interactive coding. I: Adaptivity and other settings
• Private interactive communication across an adversarial channel
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models
• Towards coding for maximum errors in interactive communication
• Towards deterministic tree code constructions

Cited in

(20)

• Making asynchronous distributed computations robust to noise
• Reliable communication over highly connected noisy networks
• Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes
• Interactive coding for multiparty protocols
• Simulating noisy channel interaction (extended abstract)
• Coding for interactive communication
• The adversarial noise threshold for distributed protocols
• Towards optimal deterministic coding for interactive communication
• Capacity of interactive communication over erasure channels and channels with feedback
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Synchronization strings: channel simulations and interactive coding for insertions and deletions
• Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture
• scientific article; zbMATH DE number 7564410 (Why is no real title available?)
• Palette-alternating tree codes
• Interactive error resilience beyond 2/7
• Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions
• Optimal error rates for interactive coding. I: Adaptivity and other settings
• Towards coding for maximum errors in interactive communication
• Fast algorithms for interactive coding
• Interactive coding with unbounded noise

This page was built for publication: Fast interactive coding against adversarial noise

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