Sub-optimality of the Han-Kobayashi region for the interference channel: Remarks on computing regions expressed by auxiliaries

Chandra Nair
Associate Professor, The Chinese University of Hong Kong
Given on: May 15th, 2015


A computable characterization of the capacity region for the two receiver interference channel, along with that of the two receiver broadcast channel, constitute two of the most fundamental open questions in network information theory. A computable achievable region proposed by Han and Kobayashi (1981) was the best-known achievable region and its optimality or sub-optimality had not been established prior to this work. In this work, we show that coding across time-slots can improve on Han-Kobayashi region (also known as multi-letter inner bounds).

The talk will be mainly about the various ideas and developments that eventually led to this result. It touches upon various computational aspects of computable regions or in other words, the study of extremal auxiliaries.

A similar result about Marton's achievable region for broadcast channels has not been found yet; and the difficulty lies precisely in the narrowing of extremal auxliaries, although significant progress has been made in this direction in the past few years.

This will be a whiteboard talk and though there is a rough outline, the talk can be steered by the audience.


Chandra Nair is an associate professor in the information engineering department at The Chinese University of Hong Kong. Nair obtained his PhD and Masters at Stanford University and his research hobbies involve knocking his head repeatedly against boulders, usually just for the fun of it.