Tutorial Speakers and Abstracts

Group testing pools together diagnostic samples to reduce the number of tests needed to identify infected members in a population. It is closely related to sparse estimation methods akin to compressive sensing, but is distinct as it only has access to a binary output of the tests (or sensed values).  The traditional work in group testing assumes “independent” infections. However, infections can be correlated according to a community structure; consider for instance families that practice social distancing, or schools that operate with student pods, there can be a strong correlation on whether members of the same community are infected or not. In this tutorial we start by reviewing traditional group testing techniques, and the proceed to discuss designs that take into account community correlations to reduce the number of tests needed and improve the accuracy of noisy testing.

Learning or exploration-exploitation problems abound in applications such as anomaly detection, target localization, dynamical system tracking, medical diagnosis, wireless body area sensor networks etc.  Initially, one is unclear about the state of the environment and the goal is to take observations that refine the understanding of the state.  If one has a series of  “experiments’’ (or queries), each of which provide information about the state, an important question is how to design that sequence of experiments to enable a decision about the environmental state as quickly as possible.  In particular, it is of interest to determine the next best experiment as a function of the past observations.  A formulation of this problem is active hypothesis testing which has been persistently studied since the 1940s.   We will review classic results in sequential decision making and informativeness and make connections to active testing and learning focusing on new results for the non-asymptotic case.  In particular, random walks and martingale theory play a large role.  We shall examine static and dynamic environments (active tracking).  We shall then apply these strategies to active matrix completion problems.

This is a three-part lecture. The first part is an introduction to polar coding, including a look at the original ideas that led to its discovery. The second part traces the evolution of polar coding into a mature technology as represented by 5G polar codes. The third part looks at 6G usage scenarios, identifies the challenges they pose for channel coding, and discusses potential polar coding solutions.

The ascendance of data science has ushered a tidal wave of interest in statistical and machine learning algorithms. With it, rose the need to find the performance limits and matching efficient algorithms for fundamental learning tasks. This short course will cover four related topics, focusing on elementary results and novel formulations that enable tight guarantees in scenarios where they otherwise seem impossible.

Beginning with the classical problem of discrete-distribution estimation, we will intuitively motivate the limit of accuracy with a given number of samples, and describe a simple algorithm achieving it. Observing that by standard definitions, arbitrary discrete distributions over large and infinite alphabet cannot be earned, we will introduce a competitive optimality measure and show that it allows for measuring and finding optimal estimation algorithms over any discrete alphabet.

Many applications do not require full distribution knowledge, and we will proceed to learn distribution functionals, such as entropy or support size. We will describe a simple universal technique that achieves optimal accuracy for essentially all learnable symmetric functionals. Observing that some important functionals such as support size cannot be learned with finitely many samples, and motivated by Ronald Fisher’s Unseen Species Problem, we will describe a “Data Amplification” approach that achieves the accuracy of standard algorithms, but with fewer samples.

Continuing to continuous distributions, we’ll briefly argue why they cannot be estimated with finitely many samples, then describe a measure that quantifies learning a large class of useful distributions. We will derive the limits of learning in this measure and describe algorithms that approach these limits.

Finally, we’ll discuss robust estimation that addresses learning when some samples are erroneous, corrupt, or even adversarial. We will show that these corruptions place a hard limit on the accuracy of many learning tasks even with infinitely many samples, and then describe several scenarios in which accurate learning can be achieved. We will also apply a simple geometric “AirTag” argument to show that many tasks can be optimally learned even without knowing the fraction of corrupt samples.

Many of the results described in this class are based on joint work with past and current students.

Classical information theory created by Claude Shannon in 1948 describes optimal tradeoffs in data compression and transmission that are achievable in the limit of long transmission times or data sequences. In classical information theory, the message  is divorced from its context, and the sole task of the code designer is to reproduce, quoting Shannon, “at one point either exactly or approximately a message selected at another point”. While classical information theory enabled the present era of global connectivity, it does not supply ready answers for emerging distributed systems, such as remotely controlled systems and distributed computation systems. Control and computation systems are extremely delay sensitive, so that coding over long blocks of observed data might not be feasible. Furthermore, information exchanges in such human-to-machine or machine-to-machine communication systems are performed with the purpose of performing a task – whether it is to precisely control the arm of a robotic surgeon or to ensure that an iterative computation algorithm converges – thus, the context, or the goal of communication, becomes important in code design. In other words, the job of the code designer is being expanded from just protecting the message from channel noise to also deciding what information about the observed data to send, given what the receiver already knows, in order to achieve the goal. To be successful, a code designer must not only understand the limits of feedback communication but also those of the control or computation algorithms in the distributed system of interest.  In this talk, I will show how to cast the above challenges in mathematical language, I will highlight recent research progress in those domains, and I will conclude with open problems.

An amazing presentation by the winner of the 2022 Padovani Lecturer Award.

Consider databases where corresponding entries are correlated but shuffled, some attributes may be missing or repeated. Similarly, consider correlated graphs where some of the graphs are missing vertex labels. Matching such databases or graphs corresponds to recovering the shuffling pattern or vertex labels by leveraging the correlation structure. Applications of database and graph matching range from privacy, where the graphs correspond to publicly and privately available information of internet users and their interactions on the web, to image segmentation and protein networks. This lecture explores how database and graph matching can be viewed from the lens of information theory, and how information theoretic tools can be used to derive theoretical guarantees as well as algorithms for matching.

Speaker Bio: Elza Erkip is an Institute Professor in the Electrical and Computer Engineering Department at New York University Tandon School of Engineering. She received the B.S. degree in Electrical and Electronics Engineering from Middle East Technical University, Ankara, Turkey, and the M.S. and Ph.D. degrees in Electrical Engineering from Stanford University, Stanford, CA, USA. Her research interests are in information theory, communication theory, and wireless communications.

Dr. Erkip is a member of the Science Academy of Turkey, a Fellow of the IEEE, and a Clarivate Highly Cited Researcher. She received the NSF CAREER award in 2001, the IEEE Communications Society WICE Outstanding Achievement Award in 2016, the IEEE Communications Society Communication Theory Technical Committee (CTTC) Technical Achievement Award in 2018, and the IEEE Communications Society Edwin Howard Armstrong Achievement Award in 2021. Her paper awards include the IEEE Communications Society Stephen O. Rice Paper Prize in 2004, the IEEE Communications Society Award for Advances in Communication in 2013 and the IEEE Communications Society Best Tutorial Paper Award in 2019. She was a member of the Board of Governors of the IEEE Information Theory Society 2012-2020, where she was the President in 2018. She was a Distinguished Lecturer of the IEEE Information Theory Society from 2013 to 2014.

Dr. Erkip has had many editorial and conference organization responsibilities. Some recent ones include IEEE International Conference on Communications, Communications Theory Symposium Technical Co-Chair in 2021; IEEE Journal on Selected Areas in Information Theory Lead Guest Editor in 2021; Asilomar Conference on Signals, Systems and Computers, MIMO Communications and Signal Processing Track Chair in 2017; IEEE Wireless Communications and Networking Conference Technical Co-Chair in 2017; IEEE Journal on Selected Areas in Communications Guest Editor in 2015; and IEEE International Symposium of Information Theory General Co-Chair in 2013.