2021 IEEE North American School of Information Theory

Tutorial 1
Prof. Wei Yu, University of Toronto
Massive Random Access and Massive MIMO
Moderator: Robert Schober, University of Erlangen

Abstract: Massive random access for machine-type communications is one of the key use cases for future cellular communication networks. This tutorial covers the system model, problem formulation, algorithmic development, and performance analysis for the massive connectivity scenario in which a large number of potential devices communicate with a base-station but with sporadic traffic. First, we show the problem of detecting the device activity patterns together with estimating the channels can be formulated as a compressed sensing problem, which can be solved using an approximate message passing (AMP) algorithm. Alternatively, if we only need the device activity patterns, it is possible to take advantage of channel hardening in the massive MIMO regime and to use a covariance approach to detect the device activities with fewer pilots. Finally, we compare with the classic carrier-sensing multiple access strategies and illustrate how feedback can significantly improve the design of the overall massive random access scheme.

Slides

Tutorial 2
Prof. Negar Kiyavash, École polytechnique fédérale de Lausanne
A Tutorial on Network Causal Inference: Theory and Applications
Moderator: Bruce Hajek, University of Illinois Urbana-Champaign

Abstract: A paramount challenge of this century is to understand and secure trustworthy operation of complex, dynamic, large-scale networks ranging from financial to transportation or biological. Causal dynamics that govern these networks is essential for understanding these networks and how to interact with them. Causal inference is an emerging field of statistics and machine learning that seeks new paradigms to model directional influences among phenomena. The course provides an overview of the state of the art in causal inference, focusing mainly on the statistical theory of structured learning in networks with both linear and nonlinear dynamics as well as data-driven models and applications in finance, computational biology, etc.

Tentative Topics: Review of required probability concepts; introduction to applications: computational neuroscience, financial markets, and social networks; Pearl causal calculus: causal Bayesian networks (CBNs), learning CBNS: faithfulness and identifiably, algorithms; Potential outcome model: counterfactuals and identification problems, graphical causal models; randomized experiments: identification of causes in randomized experiments, effect modification; causality in times series: Granger causality, more general linear predictors, beyond linear models and Granger causality, directed information graphs.

Slides

Tutorial 3
Prof. Michelle Effros, California Institute of Technology
Network Information Theory
Moderator: Gerhard Kramer, Technical University of Munich

Abstract: While much of the early work in information theory centered on communication networks with a single sender and a single receiver of information, the networks over which we communicate in practice are far more complex and dynamic. This tuturial highlights a few examples of the challenges of advancing network information theory and some of the techniques that enable us to make progress in this important area.

Tutorial 4
Prof. Douglas Stebila, University of Waterloo
Post-quantum Cryptography From the Learning with Errors Problem
Moderator: Ian Blake, University of British Columbia

Abstract: A major initiative in cryptography today is the development and standardization of post-quantum public key cryptography to replace number-theoretic public-key algorithms such as RSA and elliptic curves that would be vulnerable to attack by large-scale quantum computers. Problems on lattices are among the most promising mathematical assumptions for constructing quantum-resistant cryptosystems. In this tutorial, I will introduce lattice-based cryptography and the learning with errors problem, as well as several variants. I'll show how to construct public key encryption and digital signatures from lattice assumptions, and discuss the difficulty of breaking these cryptosystems. I'll present these works in the context of the United States National Institute of Standards and Technology (NIST) Post-Quantum Cryptography standardization project.

Slides

Tutorial 5
Prof. Lizhong Zheng, Massachusetts Institute of Technology
Understanding Deep Learning With an Information Geometric Method
Moderator: Christos Thrampoulidis, University of British Columbia

Abstract: When applying information theoretic analysis to machine learning problems, we often face the difficulty of describing the relation between a number of different distributions: the ground truth distribution, the empirical distribution of the training and the testing sets, the parameterized family of distributions we can use for approximations, the learned models and the updates in each iteration, etc. We argue in this tutorial that a good way to describe this complex situation is often a geometric approach. We introduce the machinery of a simplified information geometry analysis, with the basic techniques of local approximations and the key concepts including the Fisher information metrics, i-projection, mismatched statistics. We show some learning theory applications of these tools in the analysis of the strong data processing inequality, generalization error, model selection, as well as more applied problems like understanding deep neural networks, transfer learning and multi-modal learning problems.

Slides

Tutorial 6
Prof. David Tse, Stanford University, Padovani Lecturer
Speeding up Bitcoin
Moderator: Frank Kschischang, University of Toronto

Abstract: Bitcoin is the first blockchain protocol, invented by Nakamoto in 2008. It has excellent security properties, but it has horrible confirmation latencies. A transaction on the Bitcoin ledger can take hours to confirm. There have been many efforts in speeding up Bitcoin but they compromise on key security properties of Bitcoin. This tutorial is about Prism, our solution to the problem.

In this tutorial, you will learn:

• what is the goal of a blockchain protocol?

• how do we formalize the security properties of a blockchain protocol?

• how do we prove that Bitcoin is secure?

• why does Bitcoin have very bad latency?

• how to speed up Bitcoin while keeping its security properties?

• how are ideas from information theory, such as typicality and list decoding, useful for solving this problem?

Slides