Seminar in Discrete Mathematics - Tovohery Randrianarisoa

This week's seminar is given by our own Tovohery Randrianarisoa, Umeå universitet.

Title: On Linear Complexity of Finite Sequences: Coding Theory and Applications to

Abstract: We define two metrics on vector spaces over a finite field using the linear complexity of finite sequences. We then develop coding theory notions for these metrics and study their properties. We give a Singleton-like bound as well as constructions of subspaces achieving this bound. We also provide an asymptotic Gilbert-Varshamov-like bound for random subspaces. We show how to reduce the problem of finding codewords with a given Hamming weight into a problem of finding a vector of a given linear complexity. As a consequence, an application to a post-quantum digital signature scheme is presented.

Joint work with E. Persichetti.