2008 IEEE International Symposium on Information Theory
July 6th to 11th, 2008
Sheraton Centre Toronto Hotel
Toronto, Ontario, Canada
Tutorials
There will be 2 tutorials in the morning and 2 in the afternoon of Sunday July 6th. The tutorials will take place in the following two rooms: Windsor E+W, and Conference Room B+C.
09:00 - 12:00 (Morning)
Information-theoretic security: theory and practice
João Barros, University of Porto and MIT
Steven W. McLaughlin, Georgia Institute of Technology/Georgia Tech-Lorraine
Distributed source coding: Foundations, constructions and applications
Kannan Ramchandran, University of California at Berkeley
Sandeep Pradhan, University of Michigan
14:00 - 17:00 (Afternoon)
Information exchange in viral infections: Applications to vaccine design
Nebojsa Jojic, Microsoft Research, Redmond
Networks' challenge: Where game theory meets network optimization
Asu Ozdaglar, Massachusetts Institute of Technology
Abstracts and Bios of the presenters
Information-theoretic security: theory and practice
João Barros, University of Porto and MIT
Steven W. McLaughlin, Georgia Institute of Technology/Georgia Tech-Lorraine
Sunday Morning, July 6
A typical graduate course in cryptography and security always starts by discussing Shannon's notion of perfect secrecy - widely accepted as the strictest notion of security -, and by emphasizing its conceptual beauty. Right after that, it questions the practicality of information-theoretic security. Such an introduction, which is indeed pervasive, provides the perfect motivation for state-of-the-art encryption algorithms that are insensitive to the characteristics of the communications channel and rely on mathematical operations assumed to be hard to compute, such as prime factorization and the discrete logarithm function.
In this tutorial, we shall do exactly the opposite. First, we will present in detail the necessary tools and background for basic concepts of information theoretic security, highlighting the differences between information theoretic security and classical cryptography. Next we discuss the major achievements of information-theoretic security and then we will demonstrate its potential to strengthen significantly the security of digital communications, well beyond what can be achieved by cryptographic means alone. The basic idea is to exploit the randomness of the communication channels at the physical layer of a communications network to guarantee that the sent messages cannot be decoded by a third party maliciously eavesdropping: security is ensured not relatively to a hard mathematical problem but by the physical uncertainty inherent to the noisy channel - the crux of Shannon's information theory.
Bios
João Barros received his undergraduate education in Electrical and Computer Engineering from the Universidade do Porto (UP), Portugal and Universitaet Karlsruhe, Germany, until 1999, and the Ph.D. degree in Electrical Engineering and Information Technology from the Technische Universitaet Muenchen (TUM), Germany, in 2004. After his doctoral research on network information theory and joint source and channel coding, Dr. Barros joined the faculty of the Department of Computer Science at the Universidade do Porto, where he currently leads the Networking and Information Processing Group of the Instituto de Telecomunicações (a National Laboratory in Communications Engineering with more that 150 researchers with a PhD). The focus of his research lies in the general areas of information theory, communication networks and data security. In 2003, Dr. Barros received a Best Teaching Award from the Bavarian State Ministry of Sciences, Research and the Arts. In 2002 and 2003, he spent six months as a Fulbright scholar at Cornell University, where he worked on fundamental limits of wireless sensor networks. Dr. Barros served on several Technical Program Committees among which ISIT 2007, IEEE Globecom 2007, and IS 2007. Since July 2006, he serves as Secretary of the Board of Governors of the IEEE Information Theory Society.
Steven W. McLaughlin received the B.S. degree from Northwestern University in 1985, the M.S.E. degree from Princeton University in 1986, and the Ph.D. degree from the University of Michigan in 1992, all in electrical engineering. From 1992-1996 he was on the Electrical Engineering faculty at Rochester Institute of Technology. He joined the School of ECE at Georgia Tech in September 1996 where is now Ken Byers Professor of ECE. He is also Deputy Director of Georgia Tech Lorraine - the European Campus of the Georgia Institute of Technology - in Metz, France. His research interests are in the general area of communications and information theory. His research group has on-going projects in the areas of turbo, LDPC, and constrained codes for magnetic and optical recording; FEC and equalization for wireless and optical networks, quantum key distribution and data security; and theory of error control coding. He has published more than 200 papers in journals and conferences and holds 26 US patents. In 2005, he was President of the IEEE Information Theory Society. He is a Fellow of the IEEE and currently serves as an Associate Editor for Coding Techniques for the IEEE Transaction on Information Theory. He served as the Publications Editor for that journal from 1995-1999. He co-edited (with Sergio Verdu) Information Theory: 50 Years of Discovery (Wiley/IEEE Press, 1999).
Distributed source coding: Foundations, constructions and applications
Kannan Ramchandran, University of California at Berkeley
Sandeep Pradhan, University of Michigan
Sunday Morning, July 6
There is a rich history of distributed source coding in information theory dating back to the seminal works of Slepian and Wolf (1973) and Wyner and Ziv (1976). However, these concepts lay dormant for more than a quarter century, perhaps due to a lack of driving applications. With the recent emergence of application areas like distributed sensor networks, video-over-wireless systems, multimedia cellular telephony and multi-camera surveillance systems, and media security, there has been a renewal of interest in distributed source coding, and in the recognition of the need for constructive algorithms in order make these systems a reality.
This tutorial aims to make the concepts of distributed source coding easily accessible, and will cover the theoretical foundations, algorithmic constructions, as well as some of the emerging applications of distributed source coding. The first part will cover the theoretical foundations of distributed source coding and point out connections between this problem and other problems in multi-user information theory involving channel coding with side-information (which has its own rich applications base involving dirty-paper-coding, information hiding, and watermarking). We will focus on the key intuitions behind these concepts through illustrative examples, covering both the lossless and lossy cases. The second part of the tutorial will delve into the constructions of structured codes that can approach the theoretical performance limit, including trellis codes, and codes based on iterative decoding such as LDPC and LDGM codes. The third part will cover applications of this rich theory, and will survey the recent progress made by several research groups in building real-world distributed compression systems, particularly in the area of distributed video coding.
Bios
Kannan Ramchandran is a Professor in the EECS Department at the University of California at Berkeley. He has been on the faculty of UC Berkeley since 1999. From 1993 to 1999, he was on the faculty of the ECE Dept. at the University of Illinois at Urbana-Champaign. Dr. Ramchandran is a Fellow of the IEEE, and has won several research awards including two Best Paper awards from the IEEE Signal Processing Society (1993,1997), and several awards for best papers at conferences in his field. He was chosen as a Henry Magnuski Scholar at UIUC in 1998, was awarded the Okawa Foundation Prize at Berkeley in 2001, and was recognized with the Eli Jury Award in 1993 at Columbia University for the best thesis in the systems area. His current research interests include multi-user information theory and signal processing architectures for distributed systems, decentralized coding algorithms for large-scale sensor and ad hoc network, robust video delivery over wireless and peer-to-peer networks, multimedia security and information-hiding, and multi-scale statistical signal and image processing.
S. Sandeep Pradhan received the M.E. degree from the Electrical and Communication Engineering department, Indian Institute of Science, Bangalore, India, in 1996 and the Ph.D degree from the department of Electrical Engineering and Computer Sciences, University of California, Berkeley in 2001. Since January 2002, he has been an assistant professor in the department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor. His research interests include distributed information processing for sensor networks, multiple description coding, multi-user communication problems, and information theory. Dr. Pradhan received the 2001 Eliahu Jury award from the department of Electrical Engineering and Computer Sciences, University of California, Berkeley, for outstanding achievement in the areas of systems, signal processing, communications, and controls, and the CAREER award from the National Science Foundation.
Information exchange in viral infections: Applications to vaccine design
Nebojsa Jojic, Microsoft Research, Redmond
Sunday Afternoon, July 6
It turns out that concepts studied in the information theory community can potentially have a large impact on vaccine design and other applications in immunology. The immune system in higher-order animals involves multiple processes fine-tuned to discriminate between "self" and potentially harmful agents. Understanding the workings of the immune system is of crucial importance in modern medicine. Apart from having direct applications in vaccine design, such an understanding may provide broader insights into how biological systems fight disease and how to design drugs. However, the immune system is an information processing system evolved to monitor genetic content in the cells, which is ever-changing due to mutations and infections. Understanding the immune system and manipulating it (e.g., through vaccination) may require expertise beyond medicine and biology, and in particular from the areas of engineering that deal with digital information processing.
Simple (but widely accepted) approximations of the cellular arm of the immune system have striking similarities with systems and algorithms studied in engineering and computer science. For instance, the cellular state is advertised to the immune system through surface presentation of short strings of amino acids, taken pseudorandomly from protein sequences from the cell. The immune system can detect unusual (previously unseen) strings that tend to occur on the surface of many cells. Such cells are targeted by killer T cells as potentially infected cells which may have been hijacked by a virus, and may produce new viral particles. In addition, the distribution of killer T cells in terms of their binding preferences for different strings will be skewed towards detecting this new infection key - the string that has recently started appearing on the surface of a multitude of cells. This adaptivity allows the immune system to react swiftly to a reinfection, while still producing only a finite number of killer cells. Information transfer required for this functionality is based on protein-protein and protein-peptide binding preferences of particular families of molecules, which have recently been elucidated experimentally. With additional sequencing of individuals' immune system molecules and the sequencing of the infecting viruses, this data provides a rich source of information for testing various hypotheses about the immune system and its interaction with viral infections.
In this tutorial, I will give an ISIT-level-introduction to the cellular arm of the immune system, signs of its evolutionary optimization, and potential applications in HIV vaccine design. The ISIT community can benefit from this in two ways. Insight from the community may prove to be important for this area of medicine and biology, and on the other hand, this impressive natural system may provide insights that could be transferred to engineering.
Bio
Nebojsa Jojic received his PhD in electrical and computer engineering from the University of Illinois at Urbana-Champaign (UIUC) in 2001, where he was the recipient of the Robert T. Chien Award for excellence in research. Dr. Jojic received a Microsoft Fellowship in 2001, and since then, he has been with Microsoft Research, Redmond, where he has conducted research in the areas of computer vision, computational biology, signal processing and machine learning. In 2005, Dr. Jojic's work on computational 'epitomes' with applications in vision received honorable mention for Best Paper at the IEEE Conference on Computer Vision and Pattern Recognition. He was one of the first researchers to recognize that a potentially beneficial approach to vaccine design is to develop algorithms that construct vaccines that maximize an objective function related to protecting a population. Dr. Jojic has published over 60 papers in these areas, and is a holder of over 10 US patents. Dr. Jojic was also employed by the Hong Kong University of Science and Technology as a consultant in the area of computer vision and computer graphics, and he is on the scientific advisory board of the multi-national project, Structural and Functional Annotation of the Human Genome for Disease Study.
Networks' challenge: Where game theory meets network optimization
Asu Ozdaglar, Massachusetts Institute of Technology
Sunday Afternoon, July 6
As the need for global broadband access to information is increasing, we are witnessing an unprecendented growth in today's large-scale communication networks, such as the Internet, together with a shift towards operation by multiple independent and autonomous administrative domains. Different parts of these networks operate on the basis of different decentralized information, and serve heterogeneous users with diverse set of service requirements. Traditional network optimization approach, which entails a linear or convex programming formulation of a single objective among obedient users, is no longer sufficient for the analysis of these networks. The operation and control of today's networks require a new framework combining elements from distributed convex and non-convex optimization theory with game-theoretic (multi-agent) modeling.
In this tutorial, I will talk about recent research on game-theoretic models and distributed computational methods for resource allocation among heterogeneous agents in networks. In the first part of the talk, I will provide a brief introduction to game-theoretic models of resource allocation, with special emphasis on issues arising in networked-systems and efficiency properties of decentralized equilibria. In the second part, I will discuss issues of dynamics in multi-agent systems, particularly focusing on learning of relevant parameters and equilibrium behavior, and the effect of network topologies. I will conclude with a review of recent work on distributed implementation, optimization, and computation in large-scale multi-agent networks, and I will highlight the synergies and the remaining challenges between distributed optimization methods and game-theoretic analysis of these systems.
Bio
Asu Ozdaglar received the B.S. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1996, and the S.M. and the Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1998 and 2003, respectively.
Since 2003, she has been a member of the faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where she is currently the Class of 1943 Career Development Associate Professor. She is also a member of the Laboratory for Information and Decision Systems and the Operations Research Center. Her research interests include optimization theory, with emphasis on nonlinear programming and convex analysis, game theory, and distributed optimization methods. She is the co-author (with Dimitri P. Bertsekas and Angelia Nedic) of the book entitled "Convex Analysis and Optimization" (Athena Scientific, 2003). She is the recipient of the Graduate Student Council Teaching award and the NSF Career award.