17th International Symposium on
Mathematical Theory of Networks and Systems
Kyoto International Conference Hall, Kyoto, Japan, July 24-28, 2006

MTNS 2006 Paper Abstract

Close

Paper MoA13.4

Blondel, Vincent (Univ. Catholique de Louvain), Jungers, Raphaël (Univ. catholique de Louvain), Protasov, Vladimir (Moscow State Univ.)

On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns

Scheduled for presentation during the Regular Session "Coding Theory" (MoA13), Monday, July 24, 2006, 12:05−12:30, Room 101

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on March 28, 2024

Keywords Coding theory

Abstract

We consider questions related to the computation of the capacity of codes that avoid forbidden difference patterns. The maximal number of n-bit sequences whose pairwise differences do not contain some given forbidden difference patterns increases exponentially with n and the exponent is the capacity of the forbidden patterns. Moision, Orlitsky and Siegel proved that the capacity of a set of forbidden patterns is given by the logarithm of the joint spectral radius of a set of matrices constructed from the forbidden difference patterns. The joint spectral radius is a quantity that is in general NP-hard to compute and to approximate, and the natural question therefore arises of determining whether, due to the particular structure of the matrices involved, the capacity of a set of forbidden patterns can be computed in polynomial time. In this paper, we provide a new family of bounds that allows for the approximation, in exponential time, of the capacity with arbitrary high degree of accuracy. We also provide a polynomial time algorithm for the problem of determining if the capacity of a set is positive. Finally, we prove that the computation of the capacity of forbidden patterns defined over an extended set of symbols is a problem that is NP-hard.