Bounds on separating redundancy.

It is known that any linear code allows for a decoding strategy that treats errors and erasures separately over an error-erasure channel. In particular, a carefully designed parity-check matrix makes efficient erasure correction possible through iterative decoding while instantly providing the necessary parity-check equations for independent error correction on demand. The separating redundancy of a given linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy.