Plenary Talks

---

Information theoretic foundations of cooperation dates back to van der Meulen’s three-terminal network, and Cover and El Gamal’s seminal work on the relay channel. During the past 45 years, information theory literature has provided a wide range of fundamental results establishing benefits of cooperation in various wireless scenarios. Protocols developed to facilitate cooperation among terminals result in significant improvements in communication rates and reliability. The impending 5G wireless revolution provides the perfect setting for implementing some of these protocols and reaping the potential gains of cooperation: Large number of antennas and wide bandwidth, as in millimeter wave systems, provide abundant degrees of freedom; cloud computing and cheap storage enable enhanced computing capabilities at the network edge; full-duplex radio designs allow nodes to transcend traditional duplexing limitations; and applications such as Internet of Things provide a natural setting for cooperative communication and compression. This talk provides a brief overview of the theoretical foundations of cooperative communications along with a few examples of how even simple forms of cooperation could make big impact in future 5G wireless networks.

Elza Erkip

New York University, USA

Elza Erkip’s research interests are in multiuser information theory, communication theory, and wireless communications.

Elza Erkip received the B.S. degree in Electrical and Electronics Engineering from Middle East Technical University, Turkey, and the M.S. and Ph.D. degrees in Electrical Engineering from Stanford University. Currently, she is a Professor of Electrical and Computer Engineering with New York University Tandon School of Engineering.

Elza Erkip received the NSF CAREER award in 2001, the IEEE Communications Society Stephen O. Rice Paper Prize in 2004, the IEEE ICC Communication Theory Symposium Best Paper Award in 2007, and the IEEE Communications Society Award for Advances in Communication in 2013. She has been a member of the Board of Governors of the IEEE Information Theory Society since 2012 where she is currently the Second Vice President. She was a Distinguished Lecturer of the IEEE Information Theory Society from 2013 to 2014. She is a Fellow of the IEEE, a member of the Science Academy Society of Turkey and is among the 2014 and 2015 Thomson Reuters Highly Cited Researchers.

---

---

The Laplacian matrices of graphs are used to solve problems in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they arise in so many applications.

We then introduce ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification — the approximation of a graph by a sparser one. As an application, we explain how Laplacian system solvers can be used to quickly solve network optimization problems.

Daniel A. Spielman

Yale University, USA

D. A. Spielman’s research interests include the design and analysis of algorithms, network science, machine learning, digital communications and scientific computing.

Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor at Yale University. He is presently the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.

Among others, D. A. Spielman received the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2015 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship. He is a Fellow of the Association for Computing Machinery and a member of the Connecticut Academy of Science and Engineering.

---

---

Quantum information theory studies the laws of transmission, transformation and storage of information in the systems obeying the rules of quantum physics. One of its major achievements is the creation and thorough investigation of the concept of quantum communication channels. This has resulted in an elaborated structural theory and was accompanied by the discovery of a whole spectrum of entropic quantities characterizing the information-processing performance of the channels.

The topic of this lecture – the capacity of a quantum channel for transmitting classical information – is intended to make a bridge between the classical and the quantum theories and is especially convenient for a smooth transition from the former to the latter. Moreover, being the earliest and perhaps the most mature part of quantum Shannon theory, this topic continues to develop actively. Several recent achievements mentioned in the lecture, as well as intriguing open questions, are pertinent to this line of research.

Basing on simple matrix analysis, we begin with the demonstration of a close parallelism between classical and quantum statistical descriptions of information transmission processes; on the other hand, we stress the fundamental peculiarities of the quantum description, namely “complementarity” and “entanglement” which are absent in the classical picture.

Then we introduce a basic notion of a classical-quantum channel as a channel with classical input and quantum output, and give a brief survey of a variety of the relevant results: from the analog of Shannon’s channel coding theorem to the most recent achievements concerning error exponents, higher order asymptotics and strong converses. Next, we discuss the general concept of a (quantum) channel, its algebraic structure and the classical capacities, and touch upon the remarkable quantum phenomenon of superadditivity of information in memoryless channels due to entanglement in the decoding and encoding procedures. We then describe quantum Gaussian channels and report on the progress concerning the noncommutative analogs of Shannon’s famous capacity formula based on the recent solution of the long-standing “Gaussian optimizer conjecture”.

Finally, we comment on the “zoo” of different capacities of a quantum channel. Remarkably, in the quantum case the notion of channel capacity splits, giving a whole spectrum of information-processing characteristics depending on the kind of the data transmitted (classical or quantum) as well as on the available additional resources such as entanglement assistance or the feedback.

Alexander S. Holevo (Shannon Award)

Steklov Mathematical Institute, Russia

A. S. Holevo’s scientific interests lie in the foundations of quantum theory, quantum statistics and quantum information theory. In 1973 he obtained an upper bound for amount of classical information which can be extracted from ensemble of quantum states by quantum measurements (this result is known as Holevo’s theorem). He also developed the mathematical theory of quantum communication channels, the noncommutative theory of statistical decisions, proved coding theorems in quantum information theory and revealed the structure of quantum Markov semigroups and measurement processes.

Alexander S. Holevo graduated from Moscow Institute of Physics and Technology in 1966, defended a PhD Thesis in 1969 and a Doctor Science Thesis in 1975. Since 1986 A. S. Holevo is Professor in the Moscow State University and Moscow Institute of Physics and Technology. Among other honors, Alexander Holevo received the Andrey Markov Prize of Russian Academy of Sciences (1997), prizes for the best scientific achievements of Russian Academy of Sciences (1992, 1995, 2008), the Quantum Communication Award (1996), the Alexander von Humboldt Research Award (1999) and the Claude E. Shannon Award (2016). He is a member of Steklov Mathematical Institute, Moscow, since 1969.

---

---

Random constraint satisfaction problems have been widely studied in the past. In many systems, when the number M of random constraints and the number N of variables go simultaneously to infinity at a fixed ratio alpha=M/N, at low alphas we are in the SAT region, where there is a choice of the variables that satisfies all the constraints, while at high alpha we are in the UNSAT region, where there is no choice of the variables that satisfies all the constraints. The transition from the SAT to the UNSAT region is sharp.

Analytic computations have been done for the value of the transition point in many cases, e.g., the K-SAT problem. However, in the past, the behavior at the transition has been mostly studied in the case where the variables are Boolean. In this talk, I will describe new features that are present near and at the transition in the case where the variables are continuous. In the continuous case, the N Boolean variables are replaced by real variables belonging to an N-dimensional manifold and the usual M boolean constraints are replaced by M inequalities.

A familiar example of a continuous satisfaction problem is to find a feed-forward neural network such that M input patterns are correctly classified; here the N synaptic strengths play the role of the variables and each input pattern provides a constraint.

Giorgio Parisi

University of Rome I, La Sapienza, Italy

Giorgio Parisi is best known for his works concerning statistical mechanics, quantum field theory and various aspects of physics, mathematics and philosophy of science. Giorgio Parisi’s research focused mainly on disordered systems, in particular on spin glass theory. He suggested a crucial concept in spin glass theory, known as Parisi functional. He also found many applications of spin glass theory to optimization theory, biology and immunology.

Giorgio Parisi graduated in University of Rome La Sapienza in 1970, supervised by Nicola Cabibbo. He became a researcher at the Laboratori Nazionali di Frascati (1971–1981) while visiting Columbia University in New York (1973–1974), the Institut des Hautes Études Scientifiques (1976–1977), and the École Normale Supérieure (1977–1978). He got a Professor ordinarius position in 1981 at University of Rome Tor Vergata, and in 1992 at University of Rome La Sapienza.

Giorgio Parisi has been awarded several honors, including the the Boltzmann Medal (1992) and the Dirac Medal (1999). He also received the Enrico Fermi Award (2002), Microsoft Award (2007), Lagrange Prize (2009), Max Planck Medal (2011) and the High Energy and Particle Physics Prize – EPS HEPP Prize (2015). He is a member of the American National Academy of Sciences.

---

---

Applications of coding in communication and computer science give rise to various metrics on strings over a finite alphabet. We consider a class of metrics induced by partial orders on the code coordinates, paying special attention to one such metric (the Niederreiter-Rosenbloom-Tsfasman metric) and its applications in wireless, list decoding, approximation theory, and polar coding. We discuss combinatorics of the ordered metric space, and extend some of the results to general partial orders. We continue with several results related to distance distributions of linear codes and their extentions to the ordered case, as well as links with matroids on partial orders. In conclusion, we mention a further extension to infinite orders and an unexpected appearance of wavelet-like functions.

This line of work has developed over a number of years and draws on joint papers with many colleagues, including, in particular, (former) students Andrew McGregor, Punarbasu Purkayastna, and Woomyoung Park.

Alexander Barg

University of Maryland, USA

A. Barg’s research interests are in coding and information theory, algebraic combinatorics, and related areas of applied mathematics. Among other topics he has worked on extremal problems of coding and information theory, where he proved new bounds on the reliability function of the binary symmetric and Gaussian channels, codes on graphs, digital fingerprinting, and combinatorics of ordered metric spaces. His recent work concerns algebraic codes for storage applications.

A. Barg received a Ph.D. in electrical engineering from the Institute for Problems in Information Transmission (IPPI) of the Russian Academy of Sciences, Moscow. He has been a senior reseacher at the IPPI since 1987. He was with the Bell Laboratories of Lucent Technologies between 1997-2002. Since 2003 he has been a Professor in the University of Maryland.

A. Barg received the 2015 Information Theory Society paper award for his work with Itzhak Tamo on codes with locality constraints. At this ISIT, together with I. Tamo they are presenting a tutorial on codes with locality.