A special issue of the IEEE TRANSACTIONS ON INFORMATION THEORY will be devoted to the interplay between coding and complexity. Original research papers in the areas of coding theory, complexity theory, as well as symbolic dynamics and system theory, are sought. Papers submitted to this special issue should touch at least two of these areas.
Convolutional and trellis codes have always been closely identified with the dynamical systems (encoders) that generate them, and the complexity of such codes is traditionally expressed in terms of the attributes of minimal encoders. One of the objectives of this special issue is to further explore these connections between coding theory, system theory, and symbolic dynamics, in light of new results in this area. More recently, the subject of minimal trellis representation and trellis complexity of block codes and lattices has gained a considerable research interest. Thus, another objective of this special issue is to introduce coherent structure to the many new papers on this subject. Finally, we wish to bridge the gap between coding theory and related topics in complexity theory: papers addressing the computational complexity of traditional coding tasks as well as papers concerned with the application of coding theory to problems in algorithms and complexity theory are solicited.
Since the purpose of this special issue is to stimulate a dialogue between researchers in adjacent disciplines and document results that bridge their boundaries, papers with expository or survey content are especially welcome. Sample topics include, but are not limited to, the following:
