Organizing Committee
Abstract

In the theory of error correcting codes, a sender (Alice) wants to send a message to a receiver (Bob), over a noisy channel. Strategies for Alice and Bob have been studied since the works of Shannon and Hamming from the late 1940's, from many different communities. Coding theory is a fundamental solution to challenges that arise in communication, storage, cryptography, and others; as the world changes, our challenges in these areas change, and the scenario changes for Alice and Bob. Fueled by these new scenarios, coding theory remains a rapidly advancing area of research.

One trend in many of these new scenarios in coding theory is the need for algorithmic solutions. For many problems in coding theory, it is possible to come up with nearly optimal solutions (information-theoretically speaking) which are likely very hard for Alice and Bob to actually implement. The goal of algorithmic coding theory is to design solutions which are not only combinatorially good, but are also computationally efficient.

The goal of this workshop is to bring together researchers from several different communities -- applied math, theoretical computer science, communications and electrical engineering -- to focus on a few quickly-moving topics in algorithmic coding theory. Topics will include:

  • polar codes,
  • codes for interactive communication,
  • local decoding and coding for distributed storage, and
  • non-malleable codes.
This workshop is part of a series of NSF Secure and Trustworthy Cyberspace funded workshops designed to make mathematicians aware of issues in cybersecurity.

Confirmed Speakers & Participants

Workshop Schedule

Monday, June 13, 2016
TimeEventLocationMaterials
8:30 - 9:00Registration11th Floor Collaborative Space 
9:00 - 9:15Welcome - ICERM Director11th Floor Lecture Hall 
9:15 - 10:15Maximally recoverable codes (BONUS - Mini-tutorial on storage!) - Sergey Yekhanin, Microsoft11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45Robust Positioning Patterns - Swastik Kopparty, Rutgers University11th Floor Lecture Hall
12:00 - 2:00Break for Lunch / Free Time  
2:00 - 2:45Capacity Via Symmetry I - a New Proof for an Old Code - Marco Mondelli, Ecole Polytechnique Federale de Lausanne (EPFL)11th Floor Lecture Hall
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30Capacity Via Symmetry II - General Channels and Weight Distribution - Rudiger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL)11th Floor Lecture Hall
5:00 - 6:30Welcome Reception11th Floor Collaborative Space 
Tuesday, June 14, 2016
TimeEventLocationMaterials
9:15 - 10:15High rate locally-correctable and locally-testable codes with sub-polynomial query complexity (BONUS - Mini-tutorial on LDCs, LCCs, LTCs!) - Shubhangi Saraf, Rutgers University11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45Reliable Communication over Highly Connected Noisy Networks - Klim Efremenko, Tel-Aviv University11th Floor Lecture Hall
12:00 - 2:00Break for Lunch / Free Time  
2:00 - 2:45Towards Optimal Deterministic Coding for Interactive Communication - Noga Ron-Zewi, IAS11th Floor Lecture Hall
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30Constant-rate coding for multiparty interactive communication is impossible - Ran Gelles, Princeton University11th Floor Lecture Hall
Wednesday, June 15, 2016
TimeEventLocationMaterials
9:15 - 10:15Tamper Detection and Non-malleable codes (BONUS - Mini-tutorial on non-malleable codes!) - Daniel Wichs, Northeastern University11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45Efficient Interactive Coding with Optimal Round and Communication Blowup. - Yael Kalai, Microsoft11th Floor Lecture Hall
12:00 - 12:10Group Photo in Lecture Hall11th Floor Lecture Hall 
12:10 - 2:15Break for Lunch / Free Time  
2:15 - 3:30Coffee/Tea Break and Poster Session11th Floor Collaborative Space 
3:30 - 4:30Tutorial- Engineering challenges in coding theory - Erdal Arikan, Bilkent University11th Floor Lecture Hall
Thursday, June 16, 2016
TimeEventLocationMaterials
9:15 - 10:15List-decoding for rank-metric codes (BONUS - Mini-tutorial on list-decoding!) - Carol Wang, Carnegie Mellon University11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45Dual Channels and Dual Codes- Using Heisenberg uncertainty to achieve Shannon capacity - Joseph Renes, ETH Zurich11th Floor Lecture Hall
12:00 - 2:00Break for Lunch / Free Time  
2:00 - 2:45Recent progress on codes for worst-case deletions - Venkat Guruswami, Carnegie Mellon University11th Floor Lecture Hall
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30Explicit Two-Source Extractors and Resilient Functions - David Zuckerman, University of Texas11th Floor Lecture Hall
Friday, June 17, 2016
TimeEventLocationMaterials
9:15 - 10:15Polar Coding (BONUS - Mini-tutorial on polar codes) - Erdal Arikan, Bilkent University11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45On the Finite Length Scaling of q -ary Polar Codes - Dina Goldin, Tel Aviv University11th Floor Lecture Hall
12:00 - 2:00Break for Lunch / Free Time  
2:00 - 2:45NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem - Elena Grigorescu, Purdue University11th Floor Lecture Hall
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30Linear-time list recovery of high-rate expander codes - Brett Hemenway, University of Pennsylvania11th Floor Lecture Hall

Lecture Videos

Linear-time list recovery of high-rate expander codes

Brett Hemenway
University of Pennsylvania
June 17, 2016

Explicit Two-Source Extractors and Resilient Functions

David Zuckerman
University of Texas at Austin
June 16, 2016

Recent progress on codes for worst-case deletions

Venkat Guruswami
Carnegie Mellon University
June 16, 2016

Capacity Via Symmetry II - General Channels and Weight Distribution

Rudiger Urbanke
Ecole Polytechnique Federale de Lausanne (EPFL)
June 13, 2016

Capacity Via Symmetry I - a New Proof for an Old Code

Marco Mondelli
Ecole Polytechnique Federale de Lausanne (EPFL)
June 13, 2016

Robust Positioning Patterns

Swastik Kopparty
Rutgers University
June 13, 2016