Title: Binary code upper bounds based on semidefinite programming and
explicit block diagonalization.
Speaker: Prof. Murali. K. Srinivasan, Mathematics, IITB
Time: 3.15pm, 22/10/10, Friday
Venue: 208, First floor, Mech Engg. Building
ABSTRACT: In the 1970's, Delsarte gave a polynomial time computable upper bound on binary code size using linear programming and explicit diagonalization of the (commutative) Bose-Mesner algebra of the binary Hamming scheme. In a recent breakthrough, Lex Schrijver improved this bound. There are two main steps in this approach:
(i) Modelling the problem as an exponential size semidefinite program.
(ii) Reducing the semidefinite program to polynomial size by explicitly block diagonalizing the (noncommutative) Terwilliger algebra of the binary Hamming scheme.
In the talk he will explain Delsarte's LP approach and step (i) above.
He will say a few words about step (ii).