|
Title:A Probabilistic Method for Coding Theory
Abstract: The probabilistic method, pioneered by Erdos, is used to prove the existence of a combinatorial structure with certain properties without computing the structure explicitly. An asymmetric covering code is a subset of the set of binary n-strings such that every string can be reached by changing a limited number of 1's to 0's in some string in the specified subset. This type of code was recently introduced by J. Cooper, A. Kahng, and the speaker, along with a new direct sum construction which, via the probabilistic method, gives the asymptotic order of magnitude of the minimal size of such codes. Subsequent work on covering numbers (Sloane, Applegate, and Rains) and symmetric covering codes (Vu) will be discussed. |