Alex Samorodnitsky talked about LP bounds for coding at MIT. A few small things I wanted to jot down follow. Delsarte was the first one to attempt an LP-type bound for coding. It sounded that his work would be interesting to read as establishing the actual bound went through some algebra and some geometry. In 1989 Kalai-Linial publish a Fourier-based approach to the analysis of Delsarte’s LP. Alex suggested that this may be the first time Fourier is used in Computer Science. The LP bound, which is essentially a packing bound for the Hamming cube, has counterparts in Mathematics regarding packings in metric spaces. Alex’s latest paper (S’08) has references to all these, but it is not available yet. So a related link is a previous paper of his and Navon’s.
LP bounds for error-correcting codes - 0
|









Desire to speak? ↓