Martino Borello: Asymptotic performance of G-codes and uncertainty principle.

Coding Theory and Cryptography Seminars

The uncertainty principle is a very famous inequality in Physics, Signal Processing, and Harmonic Analysis. It compares the supports of functions and of their complex-valued Fourier transforms. In a recent paper by Evra, Kowalski, and Lubotzky a connection between the uncertainty principle and the asymptotic performance of cyclic codes was pointed out. Note that the existence of an asymptotically good family of cyclic codes is a problem open for more than half a century. In the first part of the talk, we will present some recent results about the asymptotic performance of group codes, which are a generalization of cyclic codes. In the second part, we will give an overview of conjectural and proved results about the uncertainty principle over finite fields. A naive version of this principle, which is verified by any finite field, implies that there exist sequences of cyclic codes of length n, arbitrary rate, and minimum distance Ω(n^α) for all 0 < α < 1/2.