We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Side Information Design in Zero-Error Coding for Computing.
- Authors
Charpenay, Nicolas; Le Treust, Maël; Roumy, Aline
- Abstract
We investigate the zero-error coding for computing problems with encoder side information. An encoder provides access to a source X and is furnished with side information g (Y) . It communicates with a decoder that possesses side information Y and aims to retrieve f (X , Y) with zero probability of error, where f and g are assumed to be deterministic functions. In previous work, we determined a condition that yields an analytic expression for the optimal rate R * (g) ; in particular, it covers the case where P X , Y is full support. In this article, we review this result and study the side information design problem, which consists of finding the best trade-offs between the quality of the encoder's side information g (Y) and R * (g) . We construct two greedy algorithms that give an achievable set of points in the side information design problem, based on partition refining and coarsening. One of them runs in polynomial time.
- Subjects
INFORMATION design; ERROR probability; GREEDY algorithms; POLYNOMIAL time algorithms; POINT set theory; INFORMATION theory
- Publication
Entropy, 2024, Vol 26, Issue 4, p338
- ISSN
1099-4300
- Publication type
Article
- DOI
10.3390/e26040338