Generalized sphere-packing bounds on the size of codes for combinatorial channels

Many of the classic problems of the coding theory are highly symmetric, which makes it easy to derive the sphere-packing upper bounds on the size of codes. We discuss the generalizations of the sphere-packing bounds to the arbitrary error models. These generalizations become especially important when the sizes of the error spheres are nonuniform. The best possible sphere-packing bounds are the solutions to the linear programs. We derive a series of bounds from the approximations to the packing and covering problems and study the relationships and the trade-offs between them. We show the method to obtain the upper bounds by optimizing across a family of channels that admit the same codes. We present a generalization of the local degree bound of Kulkarni and Kiyavash, and use it to improve the best-known upper bounds on the sizes of the single deletion correcting codes and the single grain error correcting codes.