Constructing error correcting codes that achieve Shannon capacity on a given memoryless channel and have efficient encoding and decoding algorithms has been a major line of recent research. In this talk, we shall discuss the error correcting capacity of codes on the binary erasure channel. We will show that sufficient symmetry alone implies a linear error correcting code achieves capacity on BEC. In particular, we shall prove the following results: (i) Consider a family of linear binary error correcting codes (parameterized by block length) approaching constant rate. Suppose the transitive group of each code is doubly symmetric and the distance satisfies log(distance)/log(block length)->1. Then this family achieves capacity on BEC. This implies that BCH codes achieve capacity on BEC. (ii) Binary Reed Muller codes achieve capacity on BEC. In this proof, we shall not use any special properties of Reed Muller codes other than the fact that their symmetry group contains GL_n(F_2) and that a family of Reed Muller codes approaching constant rate satisfies log(distance)/log(block length)->1/2.
