Princeton University

School of Engineering & Applied Science

A new VC-dimension-based outer bound for the zero-error capacity of the binary adder channel

Ofer Shayevitz, Tel Aviv University
Engineering Quadrangle B205
Monday, February 9, 2015 - 4:30pm to 5:30pm

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 Or Ordentlich.
Bio: Ofer Shayevitz received the B.Sc. from the Technion Institute of Technology, and the M.Sc and Ph.D from the Tel Aviv University, all in Electrical Engineering, in 1997, 2004 and 2009, respectively. Between 2008-2011, he was a Postdoctoral Fellow with the Information Theory and Application Center at the University of California, San Diego. He then spent 2011-2013 working as a Quantitative Analyst with the D.E. Shaw Group in New York. As of 2013, he is an Assistant Professor in the Department of EE - Systems at Tel Aviv University.