Interactive Coding with Unbounded Noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916320902119424 |
|---|---|
| author | Fargion, Eden Gelles, Ran Gupta, Meghal |
| author_facet | Fargion, Eden Gelles, Ran Gupta, Meghal |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09463 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Interactive Coding with Unbounded Noise Fargion, Eden Gelles, Ran Gupta, Meghal Data Structures and Algorithms 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. |
| title | Interactive Coding with Unbounded Noise |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.09463 |