Some constructions of maximal witness codes

Given a code C ∈ F₂ⁿ and a word c ∈ C, a witness of c is a subset W ⊆ {, 1..., n} of coordinate positions such that c differs from any other codeword c´ ∈ C on the indices in W. If any codeword posseses a witness of given length w, C is called a w-witness code. This paper gives new constructions of large w-witness codes and proves with a numerical method that their sizes are maximal for certain values of n and w. Our technique is in the spirit of Delsarte´s linear programming bound on the size of classical codes and relies on the Lovász theta number, semidefinite programming, and reduction through symmetry.