Fully comprehensive analysis with illustrative examples to code upper bounds by Delsarte and by Schrijver

Abstract

In this thesis we study the maximum size A(n d) of a binary code of word length n with minimum distance at least d The problem is NP-hard and there were two earli- est upper bounds for A(n d) introduced by Philippe Delsarte in 1973 and Alexander Schrijver in 2005 The former is based on linear programming whereas the latter on semidefinite programming The purpose of this thesis is to understand the two models via many practical examples to comprehend difficult techniques used in the models and their proofs We also write computer codes to compare numerical results between Delsarte's bound and Schrijver's bound for word length n

Date of Award	2018 Aug 29
Original language	English
Supervisor	Ruey-Lin Sheu (Supervisor)