Foto von Anmoal Porwal

M.Sc. Anmoal Porwal

Technische Universität München

Professur für Codierung und Kryptographie (Prof. Wachter-Zeh)

Postadresse

Postal:
Theresienstr. 90
80333 München

Biography

I received my M.Sc. degree in Communications Engineering in 2022 from the Technical University of Munich. Since October 2022, I have been a doctoral researcher under the supervision of Professor Antonia Wachter-Zeh.

My research interests include code-based cryptography and coding theory.

Teaching

Available Theses

Theses in Progress

NP-hardness of syndrome decoding and related problems

Keywords:
complexity theory, syndrome decoding, coding theory

Description

If a problem is shown to be NP-hard, then this gives us very strong evidence that no polynomial-time algorithm will ever solve the problem for all instances. There are many important problems in coding theory for which it is of interest to know whether we can solve them efficiently. For example: maximum likelihood decoding and finding the minimum distance of an arbitrary code. The non-existence of an efficient solver for these problems would imply that many other interesting problems in coding theory also cannot be solved efficiently. Further, while NP-hardness of a problem is not sufficient for cryptography, it is often used as a way to develop confidence that a problem will also be hard for cryptographic purposes.

In [1] and [2], it was shown that the above mentioned problems are NP-hard. The hardness of many related problems were also considered in [2] and [3]. The task of the student would be to summarize these NP-hardness results, understand which problems are known to be difficult and which ones are not and the implications of these results for coding theory and other fields.

[1] E. Berlekamp, R. McEliece, and H. van Tilborg, ‘On the inherent intractability of certain coding problems (Corresp.)’, IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384–386, May 1978, doi: 10.1109/TIT.1978.1055873.
[2] A. Vardy, ‘The intractability of computing the minimum distance of a code’, IEEE Transactions on Information Theory, vol. 43, no. 6, pp. 1757–1766, Nov. 1997, doi: 10.1109/18.641542.
[3] M. Finiasz, ‘NP-completeness of Certain Sub-classes of the Syndrome Decoding Problem’, arXiv:0912.0453 [cs], Dec. 2009. Available: http://arxiv.org/abs/0912.0453

Prerequisites

- Channel coding
- Some acquaintance with complexity theory (specifically the notion of NP-completeness) is preferable but not mandatory

Supervisor:

Anmoal Porwal