# ISIT2004 Tutorials

### Pre-Conference Half-Day Tutorial Sessions -- Sunday, June 27

These intensive 3.5 hour sessions (including a half-hour break) are perfect for researchers who want intermediate level introductions to some of the most promising recent developments in the broad area of information theory, from experts in the field. These optional sessions provide a refresher course in the fundamentals, give an overview of recent progress, and point to future opportunities. Separate registration is required. Attend one tutorial and attend the second one for half price. See the registration form for details. On-site conference registration opens at 8 a.m. on the fifth floor of the Marriott.

Tutorial 1 (9:00 a.m. - 12:30 p.m.): Ueli Maurer on Cryptography

Description

This tutorial provides an introduction to cryptography, specifically addressed at an information theory and coding theory (as opposed to computer science) audience. It covers, in a rigorous style, a selection of the most fundamental cryptographic concepts and results, as well as some recent research highlights. No specific prerequisites are assumed.

There are two types of cryptographic security. The security of a system can rely either on the computational infeasibility of breaking it (computational or complexity-theoretic security), or on the theoretical impossibility of breaking it, even using infinite computing power (information-theoretic or unconditional security). In contrast to computational security, which always relies on unproven assumptions such as the hardness of factoring large integers, information-theoretically secure systems rely on no such assumptions but tend to be less practical.

The traditional application of information theory in cryptography is for proving impossibility results, like Shannon's lower bound on the required key size for a perfect encryption system, but more recent results on information-theoretic cryptography are positive in nature, making statements about what is possible rather than what is impossible. Moreover, probability-theoretic and information-theoretic techniques have found many application in cryptographic security proofs relative to computational assumptions.

Outline
• Basic concepts and security definitions: Encryption, key agreement, authentication, digital signatures, etc.
• Information-theoretic analysis of encryption and authentication
• Privacy amplification and randomness extraction
• Secret-key agreement by public discussion
• Indistinguishability-based security definitions and proofs
• Public-key cryptography and the generic group model
• Zero-knowledge interactive proofs and the simulation paradigm
• Secret Sharing
• Broadcast (or Byzantine agreement) protocols
• Secure multi-party computation protocols
See http://www.crypto.ethz.ch/research/itc/ for research articles and an overview article entitled "Information-theoretic cryptography" (1999).

Biography

Ueli Maurer, born in 1960, is professor of computer science and head of the Information Security and Cryptography Research Group at the Swiss Federal Institute of Technology (ETH), Zurich. His research interests include information security, the theory and applications of cryptography, theoretical computer science, discrete mathematics, and information theory. Maurer graduated in electrical engineering and received his Ph.D. degree in Technical Sciences from ETH Zurich. From 1990 to 1991 he was DIMACS research fellow at the Department of Computer Science at Princeton University, and in 1992 he joined the CS Department at ETH Zurich.

He has served extensively as an editor and a member of program committees. Currently he is Editor-in-Chief of the Journal of Cryptology, Editor-in-Chief (with Ronald Rivest) of Springer Verlag's book series in Information Security and Cryptography, and serves on the Board of Directors of the International Association for Cryptologic Research (IACR). He also served as an associate editor for the IEEE Transactions on Information Theory. He is a Fellow of the IEEE, was the 2000 Rademacher Lecturer of the Department of Mathematics at Penn, and is a frequent invited speaker at scientific conferences.

Maurer holds several patents for cryptographic systems and has served as a consultant for many companies and government organizations, both at the management and the technical level. He serves on a few management and scientific advisory boards and is a co-founder of the Zurich-based security software company Seclutions.

Tutorial 2 (9:00 a.m. - 12:30 p.m.): Brendan Frey on Iterative Algorithms with Applications in Sensory Processing, Multiple Sequence Analysis and Machine Learning

Description

Many problems in science and engineering require that we take into account uncertainties in the observed data and uncertainties in the model that is used to analyze the data. Probability theory (in particular, Bayes rule) provides a way to account for uncertainty, by combining the evidence provided by the data with prior knowledge about the problem. Recently, we have seen an increasing abundance of data and computational power, and this has motivated researchers to develop techniques for solving large-scale problems that require complex chains of reasoning applied to large datasets. For example, a typical problem that my group works on will have 100,000 to 1,000,000 or more unobserved random variables. In such large-scale systems, the structure of the probability model plays a crucial role and this structure can be easily represented using a graph.

Outline
• Review of the definitions and properties of the main types of graphical models
• Factor graphs
• Bayesian networks
• Markov random fields
• Lyapunov functions that can be used to formulate approximate solutions to exact inference and parameter estimation problems (which are NP hard)
• Leading-edge, computationally efficient techniques for approximate inference
• Sum-product algorithm
• Iterative conditional modes
• EM algorithm
• Markov chain Monte Carlo methods
• Mean field techniques
• Structured variational methods
• Wake-sleep algorithm.

Throughout the tutorial, examples will be taken from the application area of computer vision, to demonstrate the concepts. However, applications in image processing, digital communications, speech processing and computational molecular biology will also be described.

Biography

Brendan J. Frey was born on August 29, 1968, in Calgary, Alberta near the foothills of the Rocky Mountains, where he enjoyed hiking and camping with his family. In 1979, he started writing computer programs, attaching sensors to his home computer, and building simple robots. His first publication (Run Magazine, 1981) describes software for simulating a generative model of images, where the pixel intensities are independent. His academic education was in the areas of physics, engineering and computer science, culminating with a doctorate from Geoffrey Hinton's Neural Networks Research Group at the University of Toronto in 1997. From 1997 to 1999, Frey was a Beckman Fellow at the University of Illinois at Urbana-Champaign, where he continues to be an adjunct faculty member in Electrical and Computer Engineering. From 1998 to 2001, he was a faculty member in Computer Science at the University of Waterloo. Currently, Frey is head of the Probabilistic and Statistical Inference Group, in the Department of Electrical and Computer Engineering at the University of Toronto. Frey consults for Microsoft Research Redmond, and various start-up companies in the Toronto-Waterloo area. He has received several awards, including the Premier's Research Excellence Award of Canada, and he has given over 40 invited talks and published over 100 papers on inference and estimation in complex probability models, with applications in machine learning, computer vision, molecular biology, audio processing, image processing and iterative decoding. In 2003, he co-chaired the Canadian Workshop on Information Theory and the Workshop on Artificial Intelligence and Statistics. He was a Co-Editor-in-Chief of the February 2000 special issue of the IEEE Transactions on Information Theory, titled Codes on Graphs and Iterative Algorithms, and is currently an Associate Editor of the IEEE Transactions on Pattern Analysis and Machine Intelligence.

Tutorial 3 (2:00 p.m. - 5:30 p.m.): Giuseppe Caire, Mohamed Oussama Damen, and Hesham El Gamal on Space-Time Coding

Description

Wireless communications are characterized by random propagation conditions commonly referred to as {\em fading channels}. Roughly, a fading channel is a linear time-varying channel whose impulse response is a random process. Reliable communication over a fading channel is made possible only through the use of diversity techniques. Since the channel response at any given time and frequency (i.e., channel dimension, or degree of freedom'') is a random variable, it is essential that each bit of information is spread over several dimensions. This can be achieved, classically, by coding in the time-frequency domain. Time duration and frequency bandwidth being expensive, the number of channel degrees of freedom for diversity can be increased in the space domain, by adding spatially separated antennas at the receiver and the transmitter. Antenna diversity reception and its synergies with channel coding have been extensively studied in the past, and several techniques are widely used in practical systems. Since the mid-90's, driven by the ever-growing demand for higher wireless link throughputs and better reliability, the research on multiple-antenna techniques has been focused on multiple-antenna transmission , rather than the conventional multiple-antenna reception. Information theoretical studies of multiple-antenna systems promised a large increase in the throughput over single antenna systems. Motivated by the theoretical promises, coding over multiple antennas (space) and over time has emerged as a powerful tool to improve the quality of service over wireless communications. An impressive amount of work has been done on this field in the last five years. This body of work involves, often with cross-fertilization and synergies, the fields of coding theory, information theory, signal processing and communications . Therefore, we will generally refer to this field as Space-Time Signaling. The impact of Space-Time Signaling techniques over today's and future wireless telecommunications standards is central, and it is expected to increase due to the ever-growing demand for better spectral efficiency and better quality of service over wireless communications.

In this tutorial, we give a comprehensive treatment of space-time signalings under different channel state information (CSI) assumptions. We provide a unified treatment of the different design approaches proposed in the literature. After reviewing the information theoretic foundations, multiple-input multiple-output (MIMO) channels modeling, and the signal design criteria, we elaborate a unified approach to the different space-time signaling schemes in the literature (e.g., orthogonal designs, trellis space-time codes, linear constellations, ...), under different CSI scenarios (i.e., adaptive, coherent, non-coherent, and differentially coherent). Similarly, we elaborate a unified approach to the receiver architecture and the signal processing of the different signaling schemes. We then discuss the diversity versus rate tradeoffs of MIMO channels under different constraints. Some classes of space-time signaling schemes achieving the optimal diversity versus rate tradeoffs are elaborated. Finally, we draw some conclusions and present some problems for future research.

For further information please see the web pages of the speakers: Caire -- Damen -- El Gamal

Outline

• Information theoretic background (using space to obtain diversity and create parallel channels).
• Space-time codes over QAM constellations (binary rank criteria).
• Linear space-time constellations (orthogonal designs and linear dispersion codes).
• Differential and training based schemes.
• Receiver architectures (iterative decoding, sphere and sequential decoding).
• The diversity-vs-rate tradeoff: Achieving the optimal diversity-vs-multiplexing tradeoff (Lattice Space-Time coding)
• Diversity from time and frequency selectivity.
• A look into distributed space-time codes in mobile ad-hoc networks (MANETs).
• Open problems, summary and conclusions.
Biographies

Giuseppe Caire was born in Torino, Italy, in 1965. He received the B.Sc. in Electrical Engineering from Politecnico di Torino (Italy) in 1990, the M.Sc. in Electrical Engineering from Princeton University in 1992, and the Ph.D. from Politecnico di Torino in 1994. He was a recipient of the AEI G.Someda Scholarship in 1991, was with the European Space Agency (ESTEC, Noordwijk, The Netherlands) from May 1994 to February 1995, and was a recipient of the COTRAO Scholarship in 1996 and a CNR Scholarship in 1997. He visited Princeton University in summer 1997 and Sydney University in summer 2000. He has been Assistant Professor in Telecommunications at the Politecnico di Torino and presently he is Professor with the Department of Mobile Communications of the Institute Eurecom, Sophia-Antipolis, France.

Dr. Caire served as Associate Editor for the IEEE Transactions on Communications in 1998-2001 and as Associate Editor for the IEEE Transactions on Information Theory in 2001-2003. In 2003 he received the Jack Neubauer Best System Paper Award from the IEEE Vehicular Technology Society. His current interests are in the field of communications theory, information theory and coding theory with particular focus on wireless applications.

Mohamed Oussama Damen received a B.Sc. degree in mathematics from the University of Paris VII in 1995, an M.Sc. degree (with honors) in digital communications systems from the Ecole Nationale Superieure des Telecommunications (ENST) de Paris, France, in 1996 and a Ph.D. degree (Summa Cum Laude) in electronics and communications from the ENST, Paris, France, in October 1999. He was a post-doctoral researcher at ENST, Paris, France, from November 1999 to August 2000, and at the Department of Electrical and Computer Engineering at the University of Minnesota from September 2000 to March 2001. In March 2001, he joined the Department of Electrical and Computer Engineering at the University of Alberta, where he is now a senior research associate of Alberta Informatics Circle of Research Excellence (ICORE). His current research interests are in the areas of communication theory, coding theory, and information theory, with a special emphasis on coding for multiple-input multiple-output (MIMO) channels.

Hesham El Gamal received the B.S. and M.S. degrees in Electrical Engineering from Cairo University, Cairo, Egypt, in 1993 and 1996, respectively, and the Ph.D. degree in Electrical and Computer Engineering from the University of Maryland at College Park, in 1999. From 1993 to 1996, he served as a Project Manager in the Middle East Regional Office of Alcatel Telecom. From 1996 to 1999, he was a Research Assistant in the Department of Electrical and Computer Engineering, the University of Maryland at College Park. From February 1999 to December 2000, he was with the Advanced Development Group, Hughes Network Systems, Germantown, Maryland, as a Senior Member of the Technical Staff. In the Fall of 1999, he served as a lecturer at the University of Maryland at College Park. Since January 2001 he has been an Assistant Professor in the Electrical Engineering Department at the Ohio State University in Columbus, Ohio. He held visiting appointments at UCLA (Fall 2002, Winter 2003) and Eurecom Institute (Summer 2003)

He is a recipient of the Hughes Networking Systems Annual Achievement Award (2000), the Ohio State University College of Engineering Lumley Research Award (2003), the Ohio State University Electrical Engineering Department FARMER Young Faculty Development Fund (2003-2008), and the National Science Foundation CAREER Award (2004). He holds 4 patents and has 9 more applications pending. He is a Senior Member of the IEEE, currently serves as an Associate Editor for Space-Time Coding and Spread Spectrum for the IEEE Transactions on Communications, and is a member of the SP4COM technical committee.

Tutorial 4 (2:00 p.m. - 5:30 p.m.): Gilles Brassard on Quantum Information Processing

Description

Quantum mechanics is perhaps the most successful scientific theory of all times. Even though it is often counterintuitive, its predictions have never been observed to be wrong, no matter how strange they appear to be. Information theory is also a very successful theory, but it is firmly rooted in classical physics, which is at best an approximation of the world in which we live. This has prevented us from tapping the full potential of Nature for information processing purposes. Classical and quantum information can be harnessed together to accomplish feats that neither could achieve alone, such as quantum computing, quantum cryptography, quantum teleportation and the computation of distributed tasks with vastly reduced communication cost. Some of these concepts are still theoretical, but others have been implemented in the laboratory.

Quantum Computers can perform more parallel computation in a single piece of hardware than would be possible for a classical computer the size of the Universe. In particular, quantum computers have the potential to bring to its knees the classical cryptographic schemes currently used on the Internet to protect transactions such as the transmission of credit card numbers. Fortunately, Quantum Cryptography makes it possible to fulfill the cryptographers' age-old dream of unconditional confidentiality in communications, regardless of the eavesdropper's computing power and technological sophistication. This technique has been implemented over tens of kilometers, both using ordinary optical fiber and through free space. Implementation via satellites is being considered. Quantum teleportation conjures up images of Star Trek, but it is not science fiction. It uses quantum nonlocality to transmit quantum information through a classical channel between entangled parties. Finally, the same quantum nonlocality gives rise to the possibility of computing in a distributed environment with the expenditure of spectacularly less information transfer between the participants than would be required classically, and sometimes we can do away with communication altogether. Speculation? Future will tell!

Outline
• Basic concepts of quantum information: qubits, measurements, transformations.
• Quantum cryptography: a simple and powerful application.
• Quantum entanglement: the soul of quantum information.
• Quantum teleportation: an application of quantum entanglement.
• Quantum computation: an exponential speedup with no classical counterpart.
• Quantum communication: exponential savings in communication needs.
• Pseudo-telepathy: sometimes communication is not needed at all.
No prior knowledge of quantum mechanics will be expected from the audience. Although not required, prior attendance to Ueli Maurer's tutorial on cryptography would be an asset.

Biography

Gilles Brassard received a Ph.D. in Computer Science from Cornell University in 1979. He has been a Professor at the Universite de Montreal since then. He was Editor-in-Chief for Journal of Cryptology from 1991 until 1997, Program Chair for Crypto '89 and Program Committee Member for Crypto '88 , 1992 IEEE Conference on Structures in Complexity Theory , Crypto '97 , and other international conferences. He is the author of three books that have been translated into 7 languages. He was awarded the E.W.R. Steacie Memorial Fellowship and the Prix Urgel-Archambault in 1992, and the Steacie Prize in 1994. He was chosen Scientist of the Year'' by La Presse in 1995, elected to the Academy of Science of the Royal Society of Canada in 1996, awarded a Killam Research Fellowship in 1997, and elected foreign member of the Latvian Academy of Science in 1998. He received the Prix Marie-Victorin in 2000, became Canada Research Chair in Quantum Information Processing in 2001 and he became Fellow of the Canadian Institute for Advanced Research in 2002. Gilles Brassard is interested in all aspects of quantum information processing, which lies at the intersection of computer science and quantum mechanics. Among his main achievements, is the co-invention of quantum cryptography, privacy amplification, quantum teleportation and quantum entanglement distillation. Home