EE Seminar: A VC-dimension-based Outer Bound for the Zero-Error Capacity of the Binary Adder Channel

~~(The talk will be given in English)

Speaker: Or Ordentlich
Institute for Problems in Mechanics, Moscow
Monday, March 23rd, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
A VC-dimension-based Outer Bound for the Zero-Error Capacity of the Binary Adder Channel
Abstract
The Binary Adder Channel (BAC) is a two-user multiple access channel whose inputs are binary and whose output is the real sum of the inputs. While the Shannon capacity region of this channel is well known, little is known regarding its zero-error capacity region, and a large gap remains between the best inner and outer bounds. In this work, we provide a new outer bound for this problem, improving the best known result by Urbanke and Li.
Our result is obtained via a confluence of combinatorial and information-theoretical arguments: Given any zero-error coding scheme for the BAC, we first construct another lower-dimensional coding scheme for the BAC with correlated messages. We then obtain a single letter outer bound for the Shannon capacity region of this more general setting, which translates back to an outer bound on the zero-error capacity of the BAC. Our construction is facilitated by introducing the notion of a "soft" VC-dimension of a codebook, which we lower bound by establishing a suitable variation of the Sauer-Perles-Shelah Lemma.

Joint work with Ofer Shayevitz.