## 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 \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.

Original language | English |
---|---|

Title of host publication | 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings |

Publisher | Institute of Electrical and Electronics Engineers |

Pages | 2449-2453 |

Number of pages | 5 |

ISBN (Electronic) | 978-1-5386-9291-2 |

DOIs | |

Publication status | Published - 26 Sept 2019 |

Externally published | Yes |

Event | 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019 |

### Conference

Conference | 2019 IEEE International Symposium on Information Theory, ISIT 2019 |
---|---|

Country/Territory | France |

City | Paris |

Period | 7/07/19 → 12/07/19 |