Technical Program

Paper Detail

Paper IDI.4.1
Paper Title On the AND-OR Interference Channel and the Sandglass Conjecture
Authors Chandra Nair, The Chinese University of Hong Kong, China; Mehdi Yazdanpanah, Goldman Sachs (HK), China
Session I.4: Interference Channel II
Presentation Lecture
Track Network Information Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract This paper is mostly a follow up on the work of Etkin and Ordentlich that studied the capacity regions of binary input deterministic interference channels. The only binary input deterministic interference channel whose capacity region is unknown (up to isomorphism) is when one receiver receives the Boolean AND of the two transmitted symbols, and the other receiver obtains the Boolean OR of the two transmitted symbols. Etkin and Ordentlich stated in the paper that they believed that time-division would be the capacity region for this interference channel. In this paper we show that one can achieve rates outside the time-division region. That time-division yields the zero-error capacity region for this setting is known as Simonyi’s sand-glass conjecture, a statement that has received considerable attention in the combinatorics community. Various upper-bounds on the sum-rate of the zero error capacity region had been proposed in the combinatorics community. In this paper we evaluate an outer bound to the (traditional notion of) capacity region due to Etkin and Ordentlich and show that this yields, surprisingly, a tighter bound that the best known bound for the sand-glass problem. Finally, we establish the capacity region of the some special classes of binary input interference channels by improving on the outer-bound proposed by Etkin and Ordentlich.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!