Incremental codes

Reference: APPROX 2001, LNCS 2129, pages 75-89. Springer-Verlag, 2001.

Abstract: We introduce the notion of incremental codes. Unlike a regular code of a given rate, which is an unordered set of elements with a large minimum distance, an incremental code is an ordered vector of elements each of whose prefixes is a good regular code (of the corresponding rate). Additionally, while the quality of a regular code is measured by its minimum distance, we measure the quality of an incremental code C by its competitive ratio, A: the minimum distance of each prefix of C has to be at most a factor of A smaller than the minimum distance of the best regular code of the same rate.

We first consider incremental codes over an arbitrary compact metric space M, and construct a 2-competitive code for M. When M is finite, the construction takes time O(|M|^2), exhausts the entire space, and is NP-hard to improve in general. We then concentrate on two specific spaces: the real interval [0,1] and, most importantly, the Hamming space F^n. For the interval [0,1] we construct an optimal (infinite) code of competitive ratio ln(4) ~ 1.386. For the Hamming space F^n (where the generic 2-competitive constructive is not efficient), we show the following. If |F| >= n, we construct optimal (and efficient) 1-competitive code that exhausts F^n (has rate 1). For small alphabets (|F| < n), we show that 1-competitive codes do not exist and provide several efficient constructions of codes achieving constant competitive ratios. In particular, our best construction has rate (1-o(1)) and competitive ratio (2+o(1)), essentially matching the bounds in the generic construction.

Keywords: Codes, Competetive ratio.