Abstracts

Information Theory Boot Camp

Tuesday, January 13th, 2015

Information Theory in Computational Complexity I
9:30 am–10:30 am
Speaker: Jaikumar Radhakrishnan, Tata Institute of Fundamental Research

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.

The second session of this talk will take place on Wednesday, January 14 from 9:30 am – 10:30 am; the third session of this talk will take place on Thursday, January 15 from 9:30 am – 10:30 am; the fourth session of this talk will take place on Friday, January 16 from 9:30 am – 10:30 am.

Coding for Modern Distributed Storage Systems I
11:00 am–12:00 pm
Speaker: Parikshit Gopalan, Microsoft Research

As more and more data moves to the cloud, there is an acute need for efficient, fault-tolerant schemes for data storage. Coding theory offers solutions for fault-tolerant storage that are potentially far more efficient than replication. At the same time, the cloud setting presents some novel challenges that the classical theory does not handle.

There are currently two distinct flavors of erasure coding schemes that address this challenge. Regenerating codes attempt to minimize the total amount of data communicated over the network in order to recreate lost data, whereas locally repairable codes (LRCs) attempt to minimize the number of reads required from other machines. Both lines of work lead to new questions about classical objects such as MDS codes.

This tutorial will be in two parts, each focusing on one of the above two lines of work. The first two lectures, given by Parikshit Gopalan, will be on locally repairable codes; the second two lectures, given by Alex Dimakis, will be on regenerating codes. Both speakers will survey the rapid recent developments in this area and the theoretical and practical challenges that lie ahead.

The second session of this talk will take place on Wednesday, January 14 from 11:00 am – 12:00 pm; the third session of this talk will take place on Thursday, January 15 from 11:00 am – 12:00 pm; the fourth session of this talk will take place on Friday, January 16 from 11:00 am – 12:00 pm.

File Coding for Modern Distributed Storage Systems I (slides)
Distribution Estimation and Applications I
1:30 pm–2:30 pm
Speaker: Alon Orlitsky, UC San Diego

Distribution estimation underlies many scientific and engineering endeavors and has therefore been studied extensively for centuries. Yet faced with modern challenges in compression, learning and statistics, researchers have recently revisited this topic with new perspectives and emphasis. Taking an information-theoretic perspective, we will explore this exciting and rapidly evolving area by addressing several related questions. What is the best estimation rate, when can structure help, why may few samples suffice, which distribution properties can be quickly evaluated, and how do these results apply to basic learning and compression tasks? Where possible, examples will accompany explanations, and we will close with several open problems.

The second session of this talk will take place on Thursday, January 15 from 1:30 pm – 2:30 pm; the third session of this talk will take place on Friday, January 16 from 1:30 pm – 2:30 pm.

Information Theory in Combinatorics I
3:00 pm–4:00 pm
Speaker: Shachar Lovett, UC San Diego

We will begin with a quick review of information theoretic notions such as entropy, conditional entropy, mutual information and information divergence. Based on these we will give information theoretic proofs of various classical results: Bregman's theorem, counting antichains, the Fredman-Komlos bound, Shearer's Lemma and its applications. Then, we will go on to see how information theoretic ideas can be used to establish various inequalities.

The second session of this talk will take place on Wednesday, January 14 from 3:00 pm – 4:00 pm.

PDF icon Information Theory in Combinatorics I & II (notes)

Wednesday, January 14th, 2015

Information Theory in Computational Complexity II
9:30 am–10:30 am
Speaker: Jaikumar Radhakrishnan, Tata Institute of Fundamental Research

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.

The first session of this talk will take place on Tuesday, January 13 from 9:30 am – 10:30 am; the third session of this talk will take place on Thursday, January 15 from 9:30 am – 10:30 am; the fourth session of this talk will take place on Friday, January 16 from 9:30 am – 10:30 am.

Coding for Modern Distributed Storage Systems II
11:00 am–12:00 pm
Speaker: Parikshit Gopalan, Microsoft Research

As more and more data moves to the cloud, there is an acute need for efficient, fault-tolerant schemes for data storage. Coding theory offers solutions for fault-tolerant storage that are potentially far more efficient than replication. At the same time, the cloud setting presents some novel challenges that the classical theory does not handle.

There are currently two distinct flavors of erasure coding schemes that address this challenge. Regenerating codes attempt to minimize the total amount of data communicated over the network in order to recreate lost data, whereas locally repairable codes (LRCs) attempt to minimize the number of reads required from other machines. Both lines of work lead to new questions about classical objects such as MDS codes.

This tutorial will be in two parts, each focusing on one of the above two lines of work. The first two lectures, given by Parikshit Gopalan, will be on locally repairable codes; the second two lectures, given by Alex Dimakis, will be on regenerating codes. Both speakers will survey the rapid recent developments in this area and the theoretical and practical challenges that lie ahead.

The first session of this talk will take place on Tuesday, January 13 from 11:00 am – 12:00 pm; the third session of this talk will take place on Thursday, January 15 from 11:00 am – 12:00 pm; the fourth session of this talk will take place on Friday, January 16 from 11:00 am – 12:00 pm.

File Coding for Modern Distributed Storage Systems II (slides)
Polar Codes I
1:30 pm–2:30 pm
Speaker: Erdal Arıkan, Bilkent University

This tutorial on polar coding will start by describing the basic information polarization concepts. This will be followed by polar code constructions and a description of the successive cancellation decoding algorithm. Some performance results, comparing polar codes with state-of-the-art codes used in the standards, will be given and the practical potential of polar codes will be discussed. Finally, a number of more recent results as well as some open problems will be presented. The tutorial is intended for graduate students as well as specialists in the field. Familiarity with basic notions of information theory and elementary knowledge of martingales will be assumed.

The second session of this talk will take place on Thursday, January 15 from 3:00 pm – 4:00 pm; the third session of this talk will take place on Friday, January 16 from 3:00 pm – 4:00 pm.

PDF icon Polar Codes (slides)
Information Theory in Combinatorics II
3:00 pm–4:00 pm
Speaker: Shachar Lovett, UC San Diego

We will begin with a quick review of information theoretic notions such as entropy, conditional entropy, mutual information and information divergence. Based on these we will give information theoretic proofs of various classical results: Bregman's theorem, counting antichains, the Fredman-Komlos bound, Shearer's Lemma and its applications. Then, we will go on to see how information theoretic ideas can be used to establish various inequalities.

The first session of this talk will take place on Tuesday, January 13 from 3:00 pm – 4:00 pm.

PDF icon Information Theory in Combinatorics I & II (notes)

Thursday, January 15th, 2015

Information Theory in Computational Complexity III
9:30 am–10:30 am
Speaker: Shachar Lovett, UC San Diego

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.

The first session of this talk will take place on Tuesday, January 13 from 9:30 am – 10:30 am; the second session of this talk will take place on Wednesday, January 14 from 9:30 am – 10:30 am; the fourth session of this talk will take place on Friday, January 16 from 9:30 am – 10:30 am.

Coding for Modern Distributed Storage Systems III
11:00 am–12:00 pm
Speaker: Alex Dimakis, University of Texas, Austin

As more and more data moves to the cloud, there is an acute need for efficient, fault-tolerant schemes for data storage. Coding theory offers solutions for fault-tolerant storage that are potentially far more efficient than replication. At the same time, the cloud setting presents some novel challenges that the classical theory does not handle.

There are currently two distinct flavors of erasure coding schemes that address this challenge. Regenerating codes attempt to minimize the total amount of data communicated over the network in order to recreate lost data, whereas locally repairable codes (LRCs) attempt to minimize the number of reads required from other machines. Both lines of work lead to new questions about classical objects such as MDS codes.

This tutorial will be in two parts, each focusing on one of the above two lines of work. The first two lectures, given by Parikshit Gopalan, will be on locally repairable codes; the second two lectures, given by Alex Dimakis, will be on regenerating codes. Both speakers will survey the rapid recent developments in this area and the theoretical and practical challenges that lie ahead.

The first session of this talk will take place on Tuesday, January 13 from 11:00 am – 12:00 pm; the second session of this talk will take place on Wednesday, January 14 from 11:00 am – 12:00 pm; the fourth session of this talk will take place on Friday, January 16 from 11:00 am – 12:00 pm.

Distribution Estimation and Applications II
1:30 pm–2:30 pm
Speaker: Alon Orlitsky, UC San Diego

Distribution estimation underlies many scientific and engineering endeavors and has therefore been studied extensively for centuries. Yet faced with modern challenges in compression, learning and statistics, researchers have recently revisited this topic with new perspectives and emphasis. Taking an information-theoretic perspective, we will explore this exciting and rapidly evolving area by addressing several related questions. What is the best estimation rate, when can structure help, why may few samples suffice, which distribution properties can be quickly evaluated, and how do these results apply to basic learning and compression tasks? Where possible, examples will accompany explanations, and we will close with several open problems.

The first session of this talk will take place on Tuesday, January 13 from 1:30 pm – 2:30 pm; the third session of this talk will take place on Friday, January 16 from 1:30 pm – 2:30 pm.

Polar Codes II
3:00 pm–4:00 pm
Speaker: Erdal Arıkan, Bilkent University

This tutorial on polar coding will start by describing the basic information polarization concepts. This will be followed by polar code constructions and a description of the successive cancellation decoding algorithm. Some performance results, comparing polar codes with state-of-the-art codes used in the standards, will be given and the practical potential of polar codes will be discussed. Finally, a number of more recent results as well as some open problems will be presented. The tutorial is intended for graduate students as well as specialists in the field. Familiarity with basic notions of information theory and elementary knowledge of martingales will be assumed.

The first session of this talk will take place on Wednesday, January 14 from 1:30 pm – 2:30 pm; the third session of this talk will take place on Friday, January 16 from 3:00 pm – 4:00 pm.

PDF icon Polar Codes (slides)

Friday, January 16th, 2015

Information Theory in Computational Complexity IV
9:30 am–10:30 am
Speaker: Jaikumar Radhakrishnan, Tata Institute of Fundamental Research

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.

The first session of this talk will take place on Tuesday, January 13 from 9:30 am – 10:30 am; the second session of this talk will take place on Wednesday, January 14 from 9:30 am – 10:30 am; the third session of this talk will take place on Thursday, January 15 from 9:30 am – 10:30 am.

Coding for Modern Distributed Storage Systems IV
11:00 am–12:00 pm
Speaker: Alex Dimakis, University of Texas, Austin

As more and more data moves to the cloud, there is an acute need for efficient, fault-tolerant schemes for data storage. Coding theory offers solutions for fault-tolerant storage that are potentially far more efficient than replication. At the same time, the cloud setting presents some novel challenges that the classical theory does not handle.

There are currently two distinct flavors of erasure coding schemes that address this challenge. Regenerating codes attempt to minimize the total amount of data communicated over the network in order to recreate lost data, whereas locally repairable codes (LRCs) attempt to minimize the number of reads required from other machines. Both lines of work lead to new questions about classical objects such as MDS codes.

This tutorial will be in two parts, each focusing on one of the above two lines of work. The first two lectures, given by Parikshit Gopalan, will be on locally repairable codes; the second two lectures, given by Alex Dimakis, will be on regenerating codes. Both speakers will survey the rapid recent developments in this area and the theoretical and practical challenges that lie ahead.

The first session of this talk will take place on Tuesday, January 13 from 11:00 am – 12:00 pm; the second session of this talk will take place on Wednesday, January 14 from 11:00 am – 12:00 pm; the third session of this talk will take place on Thursday, January 15 from 11:00 am – 12:00 pm.

Distribution Estimation and Applications III
1:30 pm–2:30 pm
Speaker: Alon Orlitsky, UC San Diego

Distribution estimation underlies many scientific and engineering endeavors and has therefore been studied extensively for centuries. Yet faced with modern challenges in compression, learning and statistics, researchers have recently revisited this topic with new perspectives and emphasis. Taking an information-theoretic perspective, we will explore this exciting and rapidly evolving area by addressing several related questions. What is the best estimation rate, when can structure help, why may few samples suffice, which distribution properties can be quickly evaluated, and how do these results apply to basic learning and compression tasks? Where possible, examples will accompany explanations, and we will close with several open problems.

The first session of this talk will take place on Tuesday, January 13 from 1:30 pm – 2:30 pm; the second session of this talk will take place on Thursday, January 15 from 1:30 pm – 2:30 pm.

Polar Codes III
3:00 pm–4:00 pm
Speaker: Erdal Arıkan, Bilkent University

This tutorial on polar coding will start by describing the basic information polarization concepts. This will be followed by polar code constructions and a description of the successive cancellation decoding algorithm. Some performance results, comparing polar codes with state-of-the-art codes used in the standards, will be given and the practical potential of polar codes will be discussed. Finally, a number of more recent results as well as some open problems will be presented. The tutorial is intended for graduate students as well as specialists in the field. Familiarity with basic notions of information theory and elementary knowledge of martingales will be assumed.

The first session of this talk will take place on Wednesday, January 14 from 1:30 pm – 2:30 pm; the second session of this talk will take place on Thursday, January 15 from 3:00 pm – 4:00 pm.

PDF icon Polar Codes (slides)