Variations on the index coding problem

Daniela Tuninetti
University of Illinois at Chicago

Abstract: Index coding is a canonical problem in network information theory in which a server has N files and is connected to N clients via a noiseless broadcast channel, where each client desires a specific files and has stored locally a subset of the other files. The index coding problem is open in general, and in known to include a number of 'difficult' problems in both wired and wireless settings. Recently, generalizations of the index coding problems have found applications in domains of content delivery. In this talk we touch upon two such variations: caching and Pliable Index CODing (PICOD).

Caching is an efficient way to reduce peak hour network traffic congestion by storing some content at a user’s local cache without knowledge of later demands. Our work investigates the two-phase, placement and delivery phase, coded caching scheme proposed by Maddah-Ali and Niesen. By using an index coding outer bound, we show the optimality of the Maddah-Ali and Niesen scheme under the conditions that the cache placement phase is restricted to be uncoded.

PICOD is a variant of the index coding problem in which a client is satisfied if it can successfully decode at least one massage that he does not already have; it models applications such as web searches. PICOD can offer an exponential improvement in the number of transmissions needed to satisfy all the clients compared to index coding. Our work elaborates on this key result when all side information sets have the same cardinality and provides a lower bound based on the index coding framework.

Bio: Daniela Tuninetti is currently a Professor within the Department of Electrical and Computer Engineering at the University of Illinois at Chicago (UIC), which she joined in 2005. Dr. Tuninetti got her Ph.D. in Electrical Engineering in 2002 from ENST/Telecom ParisTech (Paris, France, with work done at the Eurecom Institute in Sophia Antipolis, France), and she was a postdoctoral research associate at the School of Communication and Computer Science at the Swiss Federal Institute of Technology in Lausanne (EPFL, Lausanne, Switzerland) from 2002 to 2004. Dr. Tuninetti is a recipient of a best paper award at the European Wireless Conference in 2002, of an NSF CAREER award in 2007, and named UIC University Scholar in 2015. Dr. Tuninetti was the editor-in-chief of the IEEE Information Theory Society Newsletter from 2006 to 2008, an editor for IEEE Communication Letters from 2006 to 2009, and for IEEE Transactions on Wireless Communications from 2011 to 2014; she is currently an associate editor for IEEE Transactions on Information Theory. Dr. Tuninetti's research interests are in the ultimate performance limits of wireless interference networks (with special emphasis on cognition and user cooperation), coexistence between radar and communication systems, multi-relay networks, content-type coding, and caching networks.

Presentation (PDF File)

Back to Emerging Wireless Networks