Technical Program

Paper Detail

Paper Title On the Computational Complexity of Blind Detection of Binary Linear Codes
Paper IdentifierTH4.R9.1
Authors Alexios Balatsoukas-Stimming, Aris Filos-Ratsikas, École polytechnique fédérale de Lausanne (EPFL), Switzerland
Session Computational Complexity
Location Pontoise, Level 5
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 16:40 - 17:00
Manuscript  Click here to download the manuscript
Abstract 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 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 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.