Universal Codes in the Shared-randomness Model for Channels with General Distortion Capabilities

The concept of universal codes has been recently introduced in the paper `Universal codes in the shared-randomness model for channels with general distortion capabilities' [1] written by B. Bauwens and M. Zimand. Universal codes extend the idea of error-correcting codes by considering types of channels which are more general than bit-flip channels to different extents. In this work we study the problem of universal channel coding in the \textit{oblivious scenario} which is also described in [1]. In this setting a universal code has several parameters, namely, the number of messages, the code length and the shared randomness (or, equivalently, the number of random bits shared between the encoding and decoding functions, which is the logarithm of shared randomness), while the capabilities of the channel are defined by one parameter, which is its size. Naturally, an interesting question is the optimal choice of the code parameters based on the size of the channel. The article [1] features a lower bound on the required shared randomness of a universal code which is expressed through the channel size, but does not take the code length into account. This prompts the question about the exact trade-off between the parameters of the universal code based on the size of the channel. In the current work we study this question for the case of two messages and determine the exact trade-off when the code length is greater than or equal to the shared randomness. Moreover, we discuss some ideas on how to tackle the question about the trade-off when the code length is less than the shared randomness and prove a lower bound on the code length in terms of channel size for this case. Keywords: universal code, oblivious scenario, code length, shared randomness, channel size, trade-off.