A Workshop on Information Theory and Mathematics
12 April 2017 @CUHK

***************  Thank you for your participation!  ***************

Co-organized by

Hong Kong Information Society Chapter (HK-IT Chapter)


Institute of Network Coding (INC)


Institute of Theoretical Computer Science and Communications (ITCSC)


Speakers Prof. Sidharth JAGGI - IE, CUHK
  Prof. János KÖRNER - Sapienza University of Rome
  Prof. Shuo-Yen Robert LI - University of Electronic Science and Technology of China; Emeritus Professor of IE, CUHK
  Prof. Guangyue HAN - University of Hong Kong
  Prof. Pascal VONTOBEL - IE, CUHK


Date: 12 April 2017 (Wed)
Venue: Rm 121, Ho Sin Hang Engineering Building (SHB), The Chinese University of Hong Kong  (map here)


Schedule: AM
09:00 - 10:00 Prof. Sidharth JAGGI Deniable/Covert/Stealthy/LPD Communication
10:15 - 11:15 Prof. János KÖRNER Permutation Capacity of Infinite Graphs
  11:30 - 12:30 Prof. Shuo-Yen Robert LI A Connection between Sorting/Routing/Switching Networks and Lattice Theory
  14:30 - 15:30 Prof. Guangyue HAN On Continuous-Time Gaussian Channels
15:45 - 16:45 Prof. Pascal VONTOBEL Proving Properties of Error-correcting Codes and Statistical Physics Models via Factor-graph Duality and Ideas from Topology

Talk Title & Abstract

Deniable/Covert/Stealthy/LPD Communication

by  Prof. Sidharth JAGGI
The urge to communicate, to speak and be heard, is a fundamental human need. However, embedded within our increasingly sophisticated communication networks, Big Brother is often watching. There are situations where even the fact that communication is happening (not just the content of that communication), can have real-world consequences. For instance, if you are a politically active citizen in an authoritarian society with broad censorship powers, the mere fact that you are communicating with the outside world can be construed by those authorities as sufficient justification for reprisals.

There has been a flurry of recent work in the information theory community dealing with this problem. In general, this problem encompasses models of communication with dual goals. Firstly, all communication from the source (Alice) to the destination (Bob) should be reliable, i.e., the communication protocol should be resilient to random noise, and perhaps even active jamming. Secondly, if the communication is overheard by a third party (Eve), it should be deniable from Eve. That is, not only should Eve should not learn anything about the source’s message, in fact Eve should not even be able to reliably decide whether or not the source is indeed communicating to Bob. To be able to instantiate such deniability in communication, there need to be asymmetries that might exist between Bob and Eve (for instance, perhaps the noise on the channel to Eve is higher than the noise on the channel to Bob, or perhaps Eve observes only a subset of the transmissions that Bob does).

The tools used are typically information-theoretic and/or coding-theoretic in nature. Typically, deniability is formally defined in terms of a hypothesis-testing metric, and then one demands that the communication protocol that is reliable to Bob also have “high deniability”, regardless of Eve’s estimation strategy. Recently, in various communication settings (wired, wireless and quantum channels/networks), fundamental bounds on optimal rates for deniable communication, and also complementary schemes that are close to optimal.


Permutation Capacity of Infinite Graphs

by  Prof. János KÖRNER
Given an infinite graph G with the natural numbers as its vertex set, for every natural n we consider the n-length strings corresponding to the permutations of [n] and define a graph on it where two strings are adjacent if they have adjacent vertices of G somewhere in the same position. The asymptotics of the clique number of this graph leads to intriguing problems generalizing Shannon's classical concept of graph capacity. Many new problems arise. We also discuss further generalizations in which strings are replaced by graphs.


A Connection between Sorting/Routing/Switching Networks and Lattice Theory

by  Prof. Shuo-Yen Robert LI


On Continuous-Time Gaussian Channels

by  Prof. Guangyue HAN
We establish natural connections between continuous-time Gaussian feedback/memorychannels with their associated discrete-time versions in the forms of sampling and approximating theorems. It turns out that these connections, together with relevant tools from stochastic calculus, can enhance our understanding of continuous-time Gaussian channels in terms of giving alternative interpretations to some long held “folklores”, recovering known results from new perspectives, and obtaining new results inspired by the insights and ideas that come along with the connections. In particular, we derive the capacity regions of a continuous-time white Gaussian multiple access channel, a continuous-time white Gaussian interference channel, and a continuous-time white Gaussian broadcast channel; furthermore, applying the sampling and approximating theorems and the ideas and techniques in their proofs, we analyze how feedback affects the capacity regions of families of continuous-time multi-user one-hop Gaussian channels: feedback will increase the capacity regions of some continuous-time white Gaussian broadcast and interference channels, while it will not increase capacity regions of continuous-time white Gaussian multiple access channels.


Proving Properties of Error-correcting Codes and Statistical Physics Models via Factor-graph Duality and Ideas from Topology

by  Prof. Pascal VONTOBEL
The first part of this presentation is about quantum error-correction codes (QECCs). QECCS are a vital ingredient of quantum computation and quantum communication systems. In this context it is highly desirable to design QECCs that can be represented by graphical models which possess a structure that enables efficient and close-to-optimal iterative decoding. A prominent class of QECCS are so-called stabilizer QECCs, whose construction is rendered non-trivial by the fact that the stabilizer label code, a code that is associated with a stabilizer QECC, has to satisfy a certain self-orthogonality condition. We show how factor-graph duality and ideas from topology can be used to verify that codes defined by graphical models with a certain structure have this property. This approach allows us to unify a variety of known QECC constructions and to propose new QECC constructions.

The second part of this presentation is about a classical duality result of Kramers and Wannier, which expresses the partition function of the two-dimensional Ising model at low temperature in terms of the partition function of the two-dimensional Ising model at high temperature. (Such a result is useful for a variety of reasons, not the least of which is the characterization of the Ising model at low temperature by sampling the Ising model at high temperature.) We show how very similar techniques as in the first part of this presentation can be used to prove this duality result by Kramers and Wannier.

(The talk is planned to be accessible for an audience with a general background in information and coding theory.)

Based on joint work with July Li and with Ali Al-Bashabsheh.

*************** ALL ARE WELCOME ***************