EPFL

Algo+LMA

**This is an old revision of the document!**

Taken by: Nikolaos Makriyannis

Consider a set A of words of length n. If a is a word from A, we say that a subset W set of [n] is a witness for a if a can be distinguished from any other word of A by looking only at the coordinate positions in W. Now for any integer w, a w-witness set is a set A such that any word of A has a witness of length w. One of the open question regarding w-witness sets is to compute the maximal size of a w-witness set when n and w are given.

In recent years, many upper bounds on the size of codes have been improved using the technique of semi-definite programming in the spirit of Delsarte's linear programming bound. You will be asked to learn about these methods (optimisation, group theory, representations and harmonic analysis) and apply it to witness sets.

Pre-requisites : Good command in mathematics and in particular group theory and representation theory. Taste for experimental mathematics.