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

~~(The talk will be given in English)

Speaker:   Dr. Or Ordentlich
                        MIT

Tuesday, December 15th, 2015
15:00 - 16:00
Room 206, Wolfson Mechanical Engineering Bldg., Faculty of Engineering
A VC-dimension-based Outer Bound on the Zero-Error Capacity of the Binary Adder Channel

Abstract

 The notion of zero-error capacity of a channel/graph was formalized by Shannon in 1956, and has since then been the subject of many works in information theory, coding theory and combinatorics. Despite the apparent simplicity of the zero-error communication problem, it took more than 20 years until the first non-trivial case, namely, the pentagon graph, was finally solved by Lovasz. For the vast majority of interesting channels, the zero-error capacity is still not known.

We study the zero-error communication problem in a multi-user setting, where the simplest non-trivial channel model is the binary adder. This is a two-user multiple access channel whose inputs are binary and whose output is the real sum of the inputs. We derive a new outer bound (converse) on the zero-error capacity of this channel. To this end, we extend the notion of VC-dimension and prove a corresponding generalization of Sauer's Lemma, which together with new information theoretic arguments yields our bound.

Bio: Or Ordentlich completed his B.Sc. (cum laude), M.Sc. (summa cum laude) and Ph.D. studies in 2010, 2011, and 2015, respectively, all in electrical engineering at Tel Aviv University, Israel. He is currently a postdoctoral fellow in the Laboratory of Information and Decision Systems at the Massachusetts Institute of Technology (MIT), Cambridge.
Or is the recipient of the MIT - Technion Postdoctoral Fellowship, the Adams Fellowship awarded by the Israel Academy of Sciences and Humanities, the Thalheimer Scholarship for graduate students, the Advanced Communication Center (ACC) Feder Family Award for outstanding research work in the field of communication technologies (2011,2014), and the Weinstein Prize for research in signal processing (2011,2013,2014).