Tutorials


Energy Harvesting and Remotely Powered Wireless Networks

Ayfer Özgür (Stanford University), Sennur Ulukus (University of Maryland), Aylin Yener (Penn State University)
Sunday, 10:00-13:00
Room 40.002

Energy-harvesting and wireless power transfer are quickly becoming game-changing technologies for wireless systems. By eliminating bulky batteries, decoupling node deployments from the power grid, and allowing wireless nodes to operate potentially forever in a maintenance-free manner, energy harvesting and remotely powered wireless systems enable many exciting deployment models and are expected to be key-enablers for many emerging IoT applications.

From an information-theoretic perspective, this new form of powering wireless devices introduces a fundamental paradigm — energy dynamics — into communication system design. While energy is central to the design of any engineering system, its associated dynamics so far has had minimal impact on the design of communication schemes for wireless systems. This is because conventionally, the battery and the encoder operate at two drastically different time scales and communication can be accurately modeled as constrained only in terms of average power. In contrast, in a harvesting system, energy is continuously generated and consumed and is inherently random due to randomness in the harvesting process. These random energy dynamics lead to an unprecedented constraint on coding which necessitates new information, coding, communication and network-theoretic principles for wireless system design. The goal of this tutorial is to furnish the audience with significant results on the topic, both in information theory and in related areas, and point to fresh problem formulations and open research directions brought by this new paradigm.

Material

Theoretical Elements of Data Science

Jayadev Acharya (Massachusetts Institute of Technology), Alon Orlitsky (University of California, San Diego), Ananda Theertha Suresh (University of California, San Diego)
Sunday, 10:00-13:00
Room 40.004

Statistical inference is an established science with a storied past and long-lasting impact. Traditionally, it analyzed fixed-dimensional problems in the presence of asymptotically many samples. However, modern applications operate over increasingly large domains. For example, language processing uses hundreds of thousands of words, and genomic data involves millions of nucleotides. Over the past decade, researchers in diverse disciplines ranging from information theory, to computer science, machine learning, and statistics, developed new approaches to analyze and understand data over large domains. Using innovative and interdisciplinary techniques they derived non-asymptotic algorithms that are often both sample- and time-optimal.

The tutorial will cover several important results in this exciting and rapidly evolving field. It will consist of three hour-long parts, each devoted to one basic problem: distribution estimation, property estimation, and property testing. Each part will start with the traditional view, continue with one or two new problems, and conclude with examples of their solutions. The tutorial will be self-contained and presented via a unified information-theory friendly approach.


Sparse Regression Codes

Andrew Barron (Yale University), Ramji Venkataramanan (University of Cambridge)
Sunday, 10:00-13:00
Room 40.006

Developing computationally-efficient codes that approach the Shannon-theoretic limits for communication and compression has long been one of the major goals of information and coding theory. There have been significant advances towards this goal in the last couple of decades, starting with the emergence of turbo and LDPC codes in the ’90s. Recently, it has been proven that polar codes and spatially coupled LDPC codes attain the Shannon limit for several discrete-alphabet source and channel models with feasible encoding and decoding.

However, there are many communication settings where the channel or source alphabet is inherently continuous, e.g., AWGN channels and Gaussian sources. A promising candidate for such problems is a new class of codes called Sparse Superposition Codes or Sparse Regression Codes. These codes were recently introduced by Barron and Joseph for communication over the AWGN channel. Since then, it has been shown that sparse regression codes with computationally efficient encoding and decoding approach the Shannon limit for several single- and multi-user Gaussian source and channel models. This tutorial will provide a introduction to sparse regression codes, covering existing theory and algorithms, and conclude with a discussion of open problems.

Material

Quantum Information Theory

Mark M. Wilde (Louisiana State University)
Sunday, 15:00-18:00
Room 40.002

What are the ultimate limits that nature imposes on communication and what are effective procedures for achieving these limits? In order to answer these questions convincingly, we must reassess the theory of information under a “quantum lens.” That is, since quantum mechanics represents our best understanding of microscopic physical phenomena and since information is ultimately encoded into a physical system of some form, it is necessary for us to revise the laws of information established many years ago by Shannon. This is not merely an academic exercise, but instead represents one of the most exciting new frontiers for physics, mathematics, computer science, and engineering. Entanglement, superposition, and interference are all aspects of quantum theory that were once regarded as strange and in some cases, nuisances. However, nowadays, we understand these phenomena to be features that are the enabling fuel for a new quantum theory of information, in which seemingly magical possibilities such as teleportation are becoming reality. Two other notable examples are increased communication capacities of noisy communication channels and secure encryption based on physical principles. Concepts developed in the context of quantum information theory are now influencing other areas of physics as well, such as quantum gravity, condensed matter, and thermodynamics. Furthermore, quantum information theory has given us a greater understanding of the foundations of quantum mechanics and might eventually lead to a simpler set of postulates for quantum mechanics.

This tutorial will review the basics of quantum information, in an effort to enable those trained in the traditional formulation of information theory to have a grasp for what distinguishes quantum information theory from the traditional formulation. An outline is as follows:

  1. background on quantum information and connections to classical information, including density operators, channels, measurements, purification, isometric extension, coherent measurement;
  2. noiseless protocols of entanglement distribution, teleportation, super­dense coding;
  3. distance measures including trace distance and fidelity. Uhlmann’s theorem and gentle measurement;
  4. quantum entropy and entropy inequalities;
  5. protocols including Schumacher compression, classical communication, entanglement-­assisted classical communication, quantum communication. Nonadditivity of capacities and superactivation.
Material

Theory and Practice of Codes with Locality

Alexander Barg (University of Maryland), Itzhak Tamo (Tel Aviv University)
Sunday, 15:00-18:00
Room 40.004

Data coding with locality is a new direction in coding theory that has emerged as a means of increasing data reliability in distributed storage systems. The task of repairing a single failed node in the data encoding raises new questions that are not adequately addressed by traditional code designs. These questions give rise to a group of algebraic and combinatorial problems which naturally lead to the notion of locally recoverable, or LRC codes.

In the first part of this four-part tutorial we overview constructions and limitations of LRC codes with emphasis on codes over small alphabets. We present algebraic constructions of LRC codes that combine the idea of Reed-Solomon codes with the locality requirement and discuss extensions of these constructions to algebraic-geometric codes. Next we present the availability problem and algebraic constructions of codes with multiple recovery sets. Finally, we discuss the Gilbert-Varshamov bound on LRC codes and its improvement by codes on algebraic curves, as well as upper bounds derived using graph expansion and the linear programming method.

In the second part we present applied aspects of LRC codes including current solutions implemented in industry and discuss some of the existing challenges. Several constructions of LRC codes are actually used or tested in real-life distributed storage systems. We discuss examples of codes associated with systems developed by Microsoft and Facebook as well as erasure codes in free software storage platforms such as Ceph.

Next we discuss a particular class of LRC codes known as Maximally Recoverable (partial MDS) codes. This code family closely emulates MDS codes, and constructions of this kind are particularly desirable in applications. We present several constructions of MR codes, discuss their description in terms of matroids, connections to the celebrated MDS conjecture, and open problems.

We conclude by considering two types of problems on codes with locality flavor. The first one considers LRC codes where the links between the nodes are constrained by a graph, which includes also connections to index coding and guessing games on graphs. The second group of problems concerns other coding-theoretic settings with locality typically considered in computer science, including much more difficult construction questions of locally decodable and locally correctable codes, their differences from the LRC problem, and major open questions in this area.

Material