Some constructions of maximal witness codes

Given a code C is an element of F-2(n) and a word c is an element of C, a witness of c is a subset W subset of {, 1 ... , n} of coordinate positions such that c differs from any other codeword c' is an element of 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 Lovasz theta number, semidefinite programming, and reduction through symmetry.