2026-07-25T03:03:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21036 2024-09-16T06:02:39Z ddc:004 open_access

Interactive Coding with Unbounded Noise Fargion, Eden Gelles, Ran Gupta, Meghal Distributed Computation with Noisy Links Interactive Coding Noise Resilience Unbounded Noise Random Erasure-Flip Noise Interactive coding allows two parties to conduct a distributed computation despite noise corrupting a certain fraction of their communication. Dani et al. (Inf. and Comp., 2018) suggested a novel setting in which the amount of noise is unbounded and can significantly exceed the length of the (noise-free) computation. While no solution is possible in the worst case, under the restriction of oblivious noise, Dani et al. designed a coding scheme that succeeds with a polynomially small failure probability. We revisit the question of conducting computations under this harsh type of noise and devise a computationally-efficient coding scheme that guarantees the success of the computation, except with an exponentially small probability. This higher degree of correctness matches the case of coding schemes with a bounded fraction of noise. Our simulation of an N-bit noise-free computation in the presence of T corruptions, communicates an optimal number of O(N+T) bits and succeeds with probability 1-2^(-Ω(N)). We design this coding scheme by introducing an intermediary noise model, where an oblivious adversary can choose the locations of corruptions in a worst-case manner, but the effect of each corruption is random: the noise either flips the transmission with some probability or otherwise erases it. This randomized abstraction turns out to be instrumental in achieving an optimal coding scheme. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eden Fargion and Ran Gelles and Meghal Gupta 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.43 urn:nbn:de:0030-drops-210361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.43 eng https://creativecommons.org/licenses/by/4.0/legalcode