Analysis of Deterministic Binary Interference Channels Via a General Outer Bound

We present a new outer bound for the general two-user discrete memoryless interference channel (IFC) and use it to establish the capacity region of the binary erasure IFC, whose determination was left open in . We also show that there are essentially two deterministic binary IFCs, in addition to the binary erasure IFC, whose capacity regions are not obvious from previous results. We determine the capacity region of one of these and apply the aforementioned general outer bound to obtain the best available bound on the maximum achievable sum-rate for the other. We also show that the new general outer bound is tight for one-sided deterministic IFCs that belong to the class studied by El Gamal and Costa.