# Interactive information theory (12w5119)

Arriving in Banff, Alberta on Sunday, January 15 and departing Friday January 20, 2012

## Organizers

Ian Blake (University of British Columbia)
Natasha Devroye (University of Illinois at Chicago)
Ashish Khisti (University of Toronto)

## Objectives

Our goal is to facilitate the exchange of mathematical tools and ideas in order to make significant headway on open problems in two-way information theory; this is approached by bringing together established and emerging information theorists who work on three different information theoretic areas: source coding, channel coding and information theoretic metrics and applications, and all work on problems in which information flows in two-directions.
More specific goals, enabled through the workshop's format, may be summarized as:

1. The dissemination of recent research results through a series of 1/2 hour talks - these will expose experts in one area to recent results in another, promoting collaboration across the different information theory areas.
2. The introduction of more classical two-way / interactive results in each area through 1 hour tutorial talks - these will educate and re-visit results from one area in a comprehensive manner, outlining key sticking points in the hope of shedding new light onto the challenges.
3. The posing, and attack, of open problems - each attendee will be asked to present at least one focused and formulated open problem along with past methods of attack, to the group. The open problems sessions, together with ample time to meet in groups between talks and sessions and BIRS' isolated and serene atmosphere will promote collaboration.

Importance.
Communication is inherently and philosophically a two-way and interactive process. Despite this, information theory has mainly explored the fundamental limits of one-way communication and data compression. While these one-way methods may be extended to two-way scenarios, a number of examples show that treating two-way communication as two independent one-way streams is sub-optimal. Despite this, a remarkably small community has worked on two-way problems, in part because of the underlying difficulty of this problem. By bringing together experts with various perspectives all related to the information theoretic analysis of directional communication, we hope that through interaction, seminars, and brainstorming sessions, important and promising directions for two-way communications may be identified.

Relevance.
A comprehensive theory and understanding of how to best compress and communicate two-way flows of information is of mathematical interest in and of itself: the capacity of the simplest point-to-point two-way channel has been an open problem for about 50 years now and indicates a fundamental lack of understanding of how to best treat two-way information exchanges. However, the relevance of this workshop is not a strictly mathematical curiosity - a fundamental understanding of two-way communications would have repercussions far beyond information theory. While some applications such as broadcast TV or video streaming are naturally uni-directional, many educational and industrial needs and technologies of the present and future involve inherently two-way data. Cisco predicts that video-conferencing and tele-presence, a two/multi-way endeavor with repercussions in business, government and education worldwide, will increase ten fold between 2008-2013. Governments and industry recognize the increasing importance of tele-medicine, where tele-surgery requires 10 Mbps two-way communication, often enabled over satellite, cellular, or wireless broadband links. Real-time data synchronization and distributed data storage - of relevance in the ever increasing number of data centers - are other bandwidth-hungry two-way communication scenarios of importance to businesses and public safety. Finally, the ubiquitous cellular and wireless local area networks are well known to support two-way communications. Current solutions treat the transmission of the two streams of two-way data independently; this workshop would gather experts to attack the problem of finding the information theoretic limits of joint, full-two-way communication - impacting all these applications in the longer term.

Timeliness.
This would be the first workshop that explicitly focuses on interactive information theory; an old topic deemed extremely challenging and one of the holy grails'' of information theory which has seen a recent renewal of interest. In particular, directed information is being applied to a variety of contexts, and two-way information flows over networks are merging ideas from classical two-way channels with relaying and interference management ideas. As our understanding of one-way information theory is solidifying, and new tools are emerging in various interaction-related areas, the time is ripe for a workshop with a comprehensive focus on one of the next big open problems: how to communicate in a fully interactive fashion. As there is currently no other possible venue for such a small and focused meeting of scientists we feel a 5-day workshop at BIRS would be ideal in jumpstarting and energizing the movement towards an understanding of interactive information theory.