TY - GEN

T1 - On the Computational Complexity of Blind Detection of Binary Linear Codes

AU - Balatsoukas-Stimming, Alexios

AU - Filos-Ratsikas, Aris

PY - 2019/7

Y1 - 2019/7

N2 - In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes \mathcal{C} of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set \mathcal{C} only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.

AB - In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes \mathcal{C} of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set \mathcal{C} only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.

UR - http://www.scopus.com/inward/record.url?scp=85073166644&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849467

DO - 10.1109/ISIT.2019.8849467

M3 - Other contribution

T3 - IEEE International Symposium on Information Theory

ER -