Eventi: seminari, convegni

Seminari di Geometria e Algebra: 15 Maggio ore 13:30

Seminario di Geometria e Algebra

Mercoledì 15 Maggio, ore 13:30, Aula C1.16, Coppito 2

Relatore: Alessio Meneghetti
(Università degli Studi di Trento)

Titolo: The complexity of satisfying Hamming weight constraints


A fundamental problem in computational algebra is the so-called Maximum Likelihood Decoding (MLD), which is currently the basis of many post-quantum public encryption schemes. We recall some basic notions on complexity theory and we present MLD, along with a new reduction between MLD and another well-known NP-complete problem. MLD shares with some related problems (e.g. the computation of the minimum distance of linear codes, the characterisation of the nonlinearity of Boolean functions, the solution of Boolean polynomial systems) the verification of Hamming- weight constraints. We discuss this in detail and provide explicit descriptions in terms of elementary symmetric functions.
We conclude by presenting an infinite family of linear binary codes with an important and peculiar property: the ability to decode these codes would imply the decoding of any linear binary code. A complete characterization of this family has yet to be achieved, and dedicated decoding procedures have not yet been proposed.