Bombay Information Theory Seminar 2018

BITS 2018 brought together experts with interests in Information Theory. Held during January 11-14, 2018 in Mumbai, this was the second edition of the seminar. BITS 2016 was held to commemorate the birth centenary of Claude Shannon. In addition to three days of talks, BITS 2018 featured a pre-seminar tutorial.

Speakers

(slides and videos are now available)

Srikrishna Bhashyam

IIT Madras

Avhishek Chatterjee

IIT Madras

A. Chockalingam

IISc

Marco Dalai

UNIBS

Bruce Hajek

UIUC

Sidharth Jaggi

CUHK

Rahul Jain

NUS

Navin Kashyap

IISc

Ankur Kulkarni

IIT Bombay

Arya Mazumdar

UMass Amherst

Sanjoy Mitter

MIT

Chandra Murthy

IISc

Prakash Narayan

U. Maryland

Parimal Parag

IISc

Vinod Sharma

IISc

Rajesh Sundaresan

IISc

Andrew Thangaraj

IIT Madras

Himanshu Tyagi

IISc

Rahul Vaze

TIFR

Shun Watanabe

TUAT Japan

Schedule

10:30 - 11:30

Tutorial

Between Shannon and Hamming: Communication Robust to Adversarial Jamming
Sidharth Jaggi
11:30

Tea
12:00 - 13:00

Tutorial

Between Shannon and Hamming: Communication Robust to Adversarial Jamming
Sidharth Jaggi
13:00

Lunch
14:00 - 15:00

Tutorial

Between Shannon and Hamming: Communication Robust to Adversarial Jamming
Sidharth Jaggi
15:00

Tea
15:30 - 16:30

Tutorial

Between Shannon and Hamming: Communication Robust to Adversarial Jamming
Sidharth Jaggi

10:00 - 10:50

The Communication Complexity of Secret Key Generation
Navin Kashyap
10:50

Tea
11:10 - 12:00

Recent Results in Community Detection
Bruce Hajek
12:10 - 13:00

Interactive Algorithms for Clustering and Community Detection
Arya Mazumdar
13:00

Lunch
14:00 - 14:50

Channel Modulation in Wireless Communications
A. Chockalingam
14:55 - 15:25

Extra Samples Can Reduce Communication for Independence Testing
Himanshu Tyagi
15:30 - 16:00

Capacity of Queues with Queue-length Dependent Service Errors
Avhishek Chatterjee
16:00

Tea
16:30 - 17:20

New Results on Bayesian Sparse Signal Recovery
Chandra Murthy

10:00 - 10:50

A Gibbsian Approach to Load Balancing in Large Graphs
Rajesh Sundaresan
10:50

Tea
11:10 - 12:00

Variational Bayes and a Problem of Reliable Communication
Sanjoy Mitter
12:10 - 13:00

Neyman-Pearson Test and Hoeffding Test
Shun Watanabe
13:00

Lunch
14:00 - 14:50

Sampling Rate Distortion
Prakash Narayan
14:55 - 15:25

Real-Time Status Updates for Markov Sources Over Unreliable Channels
Parimal Parag
15:30 - 16:00

Asymptotically Optimal Search Policy for Odd Arm Identification
Srikrishna Bhashyam
16:00

Tea
16:30 - 17:20

Finite Blocklength Rates over a Fading Channel with CSIT and CSIR
Vinod Sharma

10:30 - 11:20

Some New Bounds on the Reliability Function of Typewriter Channels
Marco Dalai
11:20

Tea
11:40 - 12:30

Missing Mass Problem - Estimating the Probability of the Unseen
Andrew Thangaraj
12.30

Lunch
13:30 - 14:20

Recent Results in Covert Communication
Sidharth Jaggi
14:30 - 15:20

New One-shot Protocols for Classical and Quantum Communication Tasks
Rahul Jain
15.20

Tea
15:55 - 16:25

Finite Blocklength Converses in Point-to-Point and Network Information Theory: A Convex Analytic Perspective
Ankur Kulkarni
16:30 - 17:00

Energy-Delay-Distortion Problem
Rahul Vaze

VENUE

HBCSE

Jan 11

Getting there

IIT

Jan 12, 13

Getting there

TIFR

Jan 14

Getting there

ORGANIZATION

Vivek Borkar

Bikash Dey

Nikhil Karamchandani

Sibiraj Pillai

Vinod Prabhakaran

Jaikumar Radhakrishnan

The urge to communicate, to speak and to be heard, is a fundamental human desire. To be able to do is in the presence of random disturbances (due to noise introduced by the communication medium) is among the primary mandates of the field of Information Theory. Analogously, the field of Coding Theory attempts to analyze communication in the presence of adversarial noise (due to active jamming by potentially malicious third parties who wish to disrupt communication).

Despite the similarity in the objectives of Information Theory and Coding Theory, the analytical techniques used, the types of results obtained, the "styles/philosophies", and even to some extent the research communities involved in these two fields differ, partly due to fundamental differences in the fundamental models used, but also partly due to their historical roots. Broadly speaking, in the "Shannon world", noise is stochastic, and the goal is high probability of success in communication. In contrast, in the "Hamming world", noise is worst-case but bounded in magnitude, and the goal is always successful communication.

While there is already significant cross-fertilization between Information Theory and Coding Theory, this tutorial aims to focus on recent results for particular models of communication that lie in between the Shannon and Hamming worlds. Specifically, the tutorial aims to further examine the effects of

Jammer’s "causality": In the Shannon world, the noise is usually independent of the transmission. In the Hamming world, the adversary usually knows the entire transmission before deciding how to jam. Here the effect of the transmission being revealed only causally to the adversary will be examined.

Jammer's "myopicity": Often the jammer himself doesn’t hear the transmitter exactly, before having to decide his jamming pattern. Here the impact of the jammer’s interference on the channel capacity as a function of how clearly the jammer hears the transmission will be analyzed.

The tutorial will be self-contained, and start with a refresher in basic definitions and results in Information Theory (error metrics, random coding arguments) and Coding Theory (GV bound, Plotkin bound). There will then be a discussion on list-decoding as a tool of significant value in designing communication schemes. As an example of the utility of list-decoding, randomized capacities (when the encoder and decoder share common randomness unknown to the jammer), and capacities of channels with oblivious jammers will be derived. There will then be a focus on causal and/or myopic jammers, and novel impossibility bounds (jamming attacks) and achievability schemes (sometimes) meeting them, will be provided. Much of the tutorial will focus on specific adversarial channels (binary erasure or bit-flip channels, large alphabet channels, quadratically constrained channels) as examples, with results for general channels (when available) presented as addenda. As a subsidiary goal, when computationally efficient codes meeting capacity bounds can be constructed, they will be highlighted.

As sensing, control, and actuation become further integrated into modern communication infrastructures, special consideration must be given to the type of traffic generated by associated devices. Real-time decision making relies on the availability of accurate data and, as such, delivering status updates in a timely fashion is of paramount importance. In this talk, we describe a popular timeliness metric called “information age”. We also propose transmission schemes for timely updates over unreliable communication channels.

The talk will be on load balancing on a large graph. A unit of load on each edge of a graph is to be distributed between its nodes in a balanced way. On infinite graphs, it is known that the problem exhibits nonuniqueness. Recently, Anantharam and Salez extended the definition of balanced allocations on finite graphs to their local weak limits by exploiting the notion of unimodularity. They used this to settle a conjecture of Hajek on the Erdos-Renyi model. A more classical Gibbsian approach can also be used to arrive at the same result. This talk will highlight the key steps needed to make the classical approach work.

Bombay Information Theory Seminar 2018

Speakers

(slides and videos are now available)

Srikrishna Bhashyam

Avhishek Chatterjee

A. Chockalingam

Marco Dalai

Bruce Hajek

Sidharth Jaggi

Rahul Jain

Navin Kashyap

Ankur Kulkarni

Arya Mazumdar

Sanjoy Mitter

Chandra Murthy

Prakash Narayan

Parimal Parag

Vinod Sharma

Rajesh Sundaresan

Andrew Thangaraj

Himanshu Tyagi

Rahul Vaze

Shun Watanabe

Schedule

Between Shannon and Hamming: Communication Robust to Adversarial Jamming

Between Shannon and Hamming: Communication Robust to Adversarial Jamming

Between Shannon and Hamming: Communication Robust to Adversarial Jamming

Between Shannon and Hamming: Communication Robust to Adversarial Jamming

The Communication Complexity of Secret Key Generation

Recent Results in Community Detection

Interactive Algorithms for Clustering and Community Detection

Channel Modulation in Wireless Communications

Extra Samples Can Reduce Communication for Independence Testing

Capacity of Queues with Queue-length Dependent Service Errors

New Results on Bayesian Sparse Signal Recovery

A Gibbsian Approach to Load Balancing in Large Graphs

Variational Bayes and a Problem of Reliable Communication

Neyman-Pearson Test and Hoeffding Test

Sampling Rate Distortion

Real-Time Status Updates for Markov Sources Over Unreliable Channels

Asymptotically Optimal Search Policy for Odd Arm Identification

Finite Blocklength Rates over a Fading Channel with CSIT and CSIR

Some New Bounds on the Reliability Function of Typewriter Channels

Missing Mass Problem - Estimating the Probability of the Unseen

Recent Results in Covert Communication

New One-shot Protocols for Classical and Quantum Communication Tasks

Tea

Finite Blocklength Converses in Point-to-Point and Network Information Theory: A Convex Analytic Perspective

Energy-Delay-Distortion Problem

VENUE

HBCSE

Jan 11

Getting there

IIT

Jan 12, 13

Getting there

TIFR

Jan 14

Getting there

ORGANIZATION

Vivek Borkar

Bikash Dey

Nikhil Karamchandani

Sibiraj Pillai

Vinod Prabhakaran

Jaikumar Radhakrishnan