On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
From MaRDI portal
Publication:3547908
DOI10.1109/TIT.2006.883615zbMath1320.94039arXivcs/0601036OpenAlexW3098374595MaRDI QIDQ3547908
Blondel, Vincent D., Vladimir Yu. Protasov, Raphaël M. Jungers
Publication date: 21 December 2008
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0601036
approximation algorithmjoint spectral radiusNP-hardnesscoding theorycapacity of codescomplexity of capacity
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coding theorems (Shannon theory) (94A24)
Related Items
Overlap-free words and spectra of matrices ⋮ The Barabanov Norm is Generically Unique, Simple, and Easily Computed ⋮ Exact computation of joint spectral characteristics of linear operators ⋮ The finite-step realizability of the joint spectral radius of a pair of \(d \times d\) matrices one of which being rank-one ⋮ On the finiteness property for rational matrices ⋮ Efficient algorithms for deciding the type of growth of products of integer matrices ⋮ Continuity properties of the lower spectral radius ⋮ Unavoidable sets of partial words ⋮ Testing avoidability on sets of partial words is hard ⋮ Regular Sequences and the Joint Spectral Radius ⋮ Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products ⋮ Finiteness property of pairs of \(2\times 2\) sign-matrices via real extremal polytope norms ⋮ Stability of Linear Problems: Joint Spectral Radius of Sets of Matrices
