Tutorials
Codes for Distributed Computing
Sunday, 25 June 2017
9:30 AM - 1:00 PM
K2
The tutorial will showcase the importance of information theory in today and tomorrow’s distributed computing systems via two fundamental and practically relevant applications. 1) Consistent shared memory emulation; 2) Distributed Processor Matrix-Vector Multiplications, and more generally, linear algebraic operations. For each application, we will discuss (a) classical papers in computing methods for the appropriate task, (b) the current-state of the art in research and practice, and (c) how information theory can be applied to undertake a fundamental study of the performance, and improve it. Connections to practice will be established via review of practical systems, models, and experimental results.
Consistent shared memory emulation is a well known task in distributed computing with applications to modern cloud-based key value stores and computing systems. We will review the basic system model and definitions related to consistent shared memory emulation, and explain a famous shared memory emulation algorithm that uses replication to build fault tolerance. We will then describe erasure coding based algorithms and a new information-theoretic framework that studies the storage cost incurred in shared memory emulation.
Matrix-vector products are the critical building block of modern computations such as machine-learning and inference problems, and massive simulations in basic science problems. These computations are often implemented in delay and fault-prone distributed computing systems. To address these, repetition and coding techniques (e.g. in Algorithm-Based Fault Tolerance, ABFT) have been studied by the distributed and parallel computing community since the 1980s. We will review relevant literature and discuss recent advances showing how an information-theoretic approach can improve the speed, reliability, and energy-efficiency of matrix-vector products and other linear algebraic operations. Fundamental limits and coding-theoretic achievabilities will be discussed for faults/delays at two levels: processor-level, and gate-level.
Viveck R. Cadambe is an Assistant Professor in the Department of Electrical
Engineering at Pennsylvania State University. Dr. Cadambe received his Ph.D
from the University of California, Irvine in 2011. Between 2011 and 2014, he
was a postdoctoral researcher, jointly with the Electrical and Computer
Engineering (ECE) department at Boston University, and the Research Laboratory
of Electronics (RLE) at the Massachusetts Institute of Technology (MIT). Dr.
Cadambe is a recipient of the 2009 IEEE Information Theory Society Best Paper
Award, the 2014 IEEE International Symposium on Network Computing and
Applications (NCA) Best Paper Award, 2016 NSF Career Award and a finalist for
the 2016 Bell Labs prize. His interests are in information theory and coding
theory, particularly applied to wireless communication networks, and
distributed storage and computing systems.
Pulkit Grover (Ph.D. UC Berkeley'10, B.Tech.'03, M.Tech.'05 IIT Kanpur) is an
assistant professor at CMU (2013-), working on information theory, circuit
design, and biomedical engineering. His main contributions to science are
towards developing and experimentally validating a new theory of information
(fundamental limits and practical designs) for efficient (e.g. low-energy)
communication and computing by incorporating novel (noisy and noiseless)
circuit-energy models to add to classical communication models. To apply these
ideas to a variety of problems including communication, computing, sensing, and
novel biomedical systems, his lab works extensively with system, circuit, and
device engineers, neuroscientists, and doctors. Pulkit received the 2011 Eli
Jury Dissertation Award from UC Berkeley; the 2012 Leonard G. Abraham best
journal paper award from the IEEE Communications Society; several conference
best papers awards; a 2014 NSF CAREER award; and a 2015 Google Research Award.
Information Limits on Finding and Hiding Message Sources on Networks: Social Media and Cryptocurrencies
Sunday, 25 June 2017
9:30 AM - 1:00 PM
K3
Broadcasting is a common theme in networks, from the spread of diseases to the propagation of viral tweets. There is a long history of modeling and analyzing the spread of epidemics, where network and spreading models are typically derived from the real world. Problems of interest include analyzing the speed of contagion, computing a disease’s probability of extinction, and identifying the patient zero for an epidemic. Renewed interest has emerged in this topic with the advent of online networks like social media and cryptocurrencies, which ask users to broadcast content over a computer network. However, these new applications differ from epidemics in one key respect: they require the source of broadcasted messages to remain anonymous. Reasons for anonymity range from freedom of speech to financial privacy. With this added constraint comes a key advantage: network designers are often able to control the network structure and/or propagation models in computer networks. This has led to a complementary line of work that attempts to design networking stacks that inherently protect the anonymity of a message source.
In this tutorial, we present recent results on source identification and hiding in the context of applications that broadcast information over networks. We discuss models and results studied by the information theory, physics, and computer science communities. We then provide a gentle introduction to methods for source identification, including the theoretical tools needed to study these problems. We conclude by discussing recent methods for designing networks that inherently hide the source of a message. The tutorial will bring together tools from different areas like branching processes, measure concentration, and extreme value theory, all in the context of cutting-edge technologies like cryptocurrencies and anonymous social media.
Giulia Fanti is a postdoctoral researcher at the University of Illinois at
Urbana-Champaign, studying privacy-preserving technologies under Professor
Pramod Viswanath. She will join Carnegie Mellon University in 2017 as an
Assistant Professor of ECE. She previously obtained her Ph.D. and M.S. in EECS
from U.C. Berkeley under Professor Kannan Ramchandran, and her B.S. in ECE from
Olin College of Engineering in 2010. She is a recipient of the National Science
Foundation Graduate Research Fellowship, as well as a Best Paper Award at ACM
Sigmetrics 2015 for her work on anonymous rumor spreading, in collaboration
with Peter Kairouz, Prof. Sewoong Oh and Prof. Pramod Viswanath of UIUC.
Pramod Viswanath received the Ph.D. degree in electrical engineering and computer science from University of California at Berkeley in 2000. From 2000 to 2001, he was a member of research staff at Flarion technologies, NJ. Since 2001, he is on the faculty at University of Illinois at Urbana Champaign in Electrical and Computer Engineering, where he currently is a professor.
He received the Eliahu Jury Award from the EECS department of UC Berkeley in 2000, the Bernard Friedman Prize from the mathematics department of UC Berkeley in 2000, a NSF CAREER award in 2002, the Xerox faculty research award from the college of engineering of UIUC in 2010 and the Best Paper Award at the Sigmetrics conference in 2015. He is a coauthor, with David Tse, of the text Fundamentals of Wireless Communication, which has been used in over 60 institutions around the world. He is coinventor of the opportunistic beamforming method and codesigner of Flash-OFDM communication algorithms used in fourth-generation cellular systems.
He was an Associate Editor of the IEEE Transactions on Information Theory from 2006 to 2008, the Technical Program co-chair of the Information Theory Workshops in 2010 and 2015 and the Technical Program co-chair of the Allerton conference in 2007 and 2008.
His current research interests are in machine learning and natural language processing. In the past he has worked on, and continues to hold interest in, information theory and its applications in various fields, including wireless communication and data privacy.
Information Theoretic Cryptography for Information Theorists
Sunday, 25 June 2017
2:00 PM - 5:30 PM
K3
Information theory has been essential for the development of theoretical cryptography right from its inception. Classic cryptography borrowed information theoretic formalisms to quantify the information leaked to an adversary. Modern cryptography adopted a computational notion of secrecy and diverged from information theory. Nevertheless, information theoretic tools and concepts remain pivotal in cryptography: Min entropy provides a basic measure of randomness on which the rich theory of pseudorandomness rests; information theoretic reduction arguments connecting the security of various cryptographic primitives abound; the versatile chain rules for Kullback-Leibler divergence and for total variation distance are often creatively used to derive performance bounds. Many recent theoretical results in randomness extraction and secure multiparty computation rely on a clever application of information theoretic concepts.
Parallel to these developments, the area of information theoretic cryptography (ITC) has studied basic primitives of cryptography under information theoretic secrecy. As is well known, ITC is not possible from scratch. However, if additional correlated sources are available for legitimate parties, ITC is not only possible, but perhaps can be realized more efficiently than computational secrecy. The basic results of ITC, interesting in their own right, constitute an important reduction tool for cryptography. Furthermore, they are closely related to coding theorems of information theory.
In this tutorial, we review the basics of ITC. Particular attention will be paid to randomness extraction, multiparty secret key agreement, and interactive protocols. We shall cover developments which span over three decades, with an emphasis on recent advances. Our effort will be to bridge the gap in the jargon of the information theory and cryptography communities, particularly to present to an information theory audience the key information theoretic ideas that have been gainfully applied in cryptography. This tutorial will be self-contained and only a basic knowledge of information theory will be assumed. It will be divided into 6 modules covering broadly the following topics: Randomness extraction and leftover hash lemma; secret key agreement and fuzzy extractors; techniques for proving impossibility (converse) bounds; secure computing and efficient reductions among complete secure functionalities; interactive secret key agreement schemes.
Himanshu Tyagi is an Assistant Professor at the Indian Institute of Science in
Bangalore. He received his B.Tech. and M.Tech. degree in Electrical Engineering
from the Indian Institute of Technology, Delhi and his Ph.D. degree from the
University of Maryland, College Park in 2013. He was a postdoctoral researcher
at the Information Theory and Applications center of the University of
California, San Diego from 2013 to 2014 and a visiting fellow at the Institute
of Henri Poincare in Paris from March to April 2016. His current research
interests include information theory and computer science, with focus on
distributed compression, interactive communication, secrecy and privacy, and
inference.
Shun Watanabe received the B.E., M.E., and Ph.D. degrees from the Tokyo Institute of Technology in 2005, 2007, and 2009, respectively. During April 2009 to February 2015, he was an Assistant Professor in the Department of Information Science and Intelligent Systems at the University of Tokushima. During April 2013 to March 2015, he was a visiting Assistant Professor in the Institute for Systems Research at the University of Maryland, College Park. During March to April 2016, he was a visiting fellow at the Institute of Henri Poincare. Since February 2015, he has been an Associate Professor in the Department of Computer and Information Sciences at Tokyo University of Agriculture and Technology. His current research interests are in the areas of information theory, quantum information theory, cryptography, and computer science.
He currently serves as an Associate Editor for the IEEE Transactions on Information Theory.
Statistical Foundations of Interactive Learning
Sunday, 25 June 2017
2:00 PM - 5:30 PM
K2
Accurate predictors that can perform tasks such as recognize objects in images, detect sentiments in text, and so on, are fundamental building blocks of modern machine learning. Developing these predictors often requires a large amount of annotated data; while vast quantities of raw or unannotated data is readily available, annotation requires human/expert attention and is expensive. A popular approach to mitigating the cost of annotation is interaction – where one or more annotators are interactively asked to label useful examples that in turn can be used to incrementally improve the accuracy of a predictor. This gives rise to the field of interactive learning – how to use human interaction to improve the performance of machine learning classifiers. The first challenge in exploiting complex feedback is that human responses are inherently imperfect, non-binary, and inconsistent across annotators.
This tutoral will cover the statistical foundations of interactive learning in three parts. The first two will focus on the foundations of basic active learning, where the goal is to learn a classifier based on label feedback from a learner. There are two major query models in interactive learning – membership query and PAC; the first two sections will focus on how to develop active learning algorithms in these two models while dealing with imperfect and hesitant labelers. In this context, we not only review the prior work in this area but also catalog extensions and open problems. In the third section of the tutorial, we will explore two recent directions in interactive learning that go beyond simple label feedback – learning from multiple annotators, and learning from more complex queries. In these scenarios, we will investigate the process of designing queries and the possible gains both in the context of prior work as well as further extensions and open problems.
Kamalika Chaudhuri received a Bachelor of Technology degree in Computer Science and Engineering in 2002 from Indian Institute of Technology, Kanpur, and a PhD in Computer Science from University of California at Berkeley in 2007. She held a postdoctoral researcher position at the Information Theory and Applications Center at UC San Diego from 2007-2009, and a postdoctoral researcher position in the CSE department at UC San Diego from 2009-2010. In July 2010, she joined the CSE department at UC San Diego as an assistant professor.
Kamalika's research interests are in the statistical foundations of machine learning. She is particularly interested in interactive learning, where the goal is to learn predictors based on interactive human feedback, as well as privacy-preserving learning, where the goal is to learn from sensitive data while preserving the privacy of individuals in the data.
Kamalika is currently on the Steering Committee of the Conference on Learning Theory (COLT), and was the Program Co-Chair of the 26th International Conference on Algorithmic Learning Theory (ALT). She received an NSF CAREER Award in 2013 and a Hellman Faculty Fellowship in 2012. She was a tutorial speaker at the GlobalSIP Conference 2014, and a keynote speaker at the 19th Annual Conference on Artificial Intelligence and Statistics (AISTATS) in 2016 and the Machine Learning Conference at the New York Academy of Sciences in 2017.
Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received her MS degrees in electrical engineering (systems) and in applied mathematics (stochastic analysis) from the University of Michigan, Ann Arbor, in 1998 and 1999, respectively. She received her Ph.D. in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 2002.
From 2002 to 2004, Tara Javidi was an assistant professor at the Electrical Engineering Department, University of Washington, Seattle. In 2005, she joined the University of California, San Diego, where she is currently a professor of electrical and computer engineering. At the University of California, San Diego, Tara Javidi directs the Advanced Networking Science Lab and is an active member of the Centers of Information Theory and Applications, Wireless Communications, Networked Systems, and Integrated Access Network.
Tara Javidi’s research interests are in communication networks, stochastic resource allocation, stochastic control theory, and wireless communications. She was the guest editor for the IEEE Journal of Selected Areas in Communications special issue on Communications and Control. From 2011 to 2014, she was an associate editor for ACM/IEEE Transactions on Networking and the editor for the IEEE Information Theory Society Newsletter. She currently serves as an associate editor for IEEE Transactions on Information Theory and IEEE Transactions on Network Science and Engineering. Furthermore, she is currently on the board of the series "Foundations and Trends in Communications and Information Theory."
Tara Javidi was a recipient of the National Science Foundation early career award (CAREER) in 2004, Barbour Graduate Scholarship, University of Michigan, in 1999, and the Presidential and Ministerial Recognitions for Excellence in the National Entrance Exam, Iran, in 1992. She was a tutorial speaker at the International Conference on Cognitive Radio Oriented Wireless Networks (CROWNCOM) 2010, ACM International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc) 2013, International Symposium on Information Theory (ISIT) 2014, and IEEE Conference on Decision and Control (CDC) 2016. Tara Javidi is a Distinguished Lecturer of the IEEE Information Theory Society (2017/18).