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.

Image for "Algorithmic Coding Theory"

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, June 13, 2016
TimeEventLocationMaterials
8:30 - 9:00am EDTRegistration11th Floor Collaborative Space 
9:00 - 9:15am EDTWelcome - ICERM Director11th Floor Lecture Hall 
9:15 - 10:15am EDTMaximally recoverable codes (BONUS - Mini-tutorial on storage!) - Sergey Yekhanin, Microsoft11th Floor Lecture Hall
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45am EDTRobust Positioning Patterns - Swastik Kopparty, Rutgers University11th Floor Lecture Hall
12:00 - 2:00pm EDTBreak for Lunch / Free Time  
2:00 - 2:45pm EDTCapacity 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:45pm EDTCoffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30pm EDTCapacity Via Symmetry II - General Channels and Weight Distribution - Rudiger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL)11th Floor Lecture Hall
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, June 14, 2016
TimeEventLocationMaterials
9:15 - 10:15am EDTHigh 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:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45am EDTReliable Communication over Highly Connected Noisy Networks - Klim Efremenko, Tel-Aviv University11th Floor Lecture Hall
12:00 - 2:00pm EDTBreak for Lunch / Free Time  
2:00 - 2:45pm EDTTowards Optimal Deterministic Coding for Interactive Communication - Noga Ron-Zewi, IAS11th Floor Lecture Hall
3:00 - 3:45pm EDTCoffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30pm EDTConstant-rate coding for multiparty interactive communication is impossible - Ran Gelles, Princeton University11th Floor Lecture Hall
Wednesday, June 15, 2016
TimeEventLocationMaterials
9:15 - 10:15am EDTTamper Detection and Non-malleable codes (BONUS - Mini-tutorial on non-malleable codes!) - Daniel Wichs, Northeastern University11th Floor Lecture Hall
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45am EDTEfficient Interactive Coding with Optimal Round and Communication Blowup. - Yael Kalai, Microsoft11th Floor Lecture Hall
12:00 - 12:10pm EDTGroup Photo in Lecture Hall11th Floor Lecture Hall 
12:10 - 2:15pm EDTBreak for Lunch / Free Time  
2:15 - 3:30pm EDTCoffee/Tea Break and Poster Session11th Floor Collaborative Space 
3:30 - 4:30pm EDTTutorial- Engineering challenges in coding theory - Erdal Arikan, Bilkent University11th Floor Lecture Hall
Thursday, June 16, 2016
TimeEventLocationMaterials
9:15 - 10:15am EDTList-decoding for rank-metric codes (BONUS - Mini-tutorial on list-decoding!) - Carol Wang, Carnegie Mellon University11th Floor Lecture Hall
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45am EDTDual Channels and Dual Codes- Using Heisenberg uncertainty to achieve Shannon capacity - Joseph Renes, ETH Zurich11th Floor Lecture Hall
12:00 - 2:00pm EDTBreak for Lunch / Free Time  
2:00 - 2:45pm EDTRecent progress on codes for worst-case deletions - Venkat Guruswami, Carnegie Mellon University11th Floor Lecture Hall
3:00 - 3:45pm EDTCoffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30pm EDTExplicit Two-Source Extractors and Resilient Functions - David Zuckerman, University of Texas11th Floor Lecture Hall
Friday, June 17, 2016
TimeEventLocationMaterials
9:15 - 10:15am EDTPolar Coding (BONUS - Mini-tutorial on polar codes) - Erdal Arikan, Bilkent University11th Floor Lecture Hall
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:00 - 11:45am EDTOn the Finite Length Scaling of q -ary Polar Codes - Dina Goldin, Tel Aviv University11th Floor Lecture Hall
12:00 - 2:00pm EDTBreak for Lunch / Free Time  
2:00 - 2:45pm EDTNP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem - Elena Grigorescu, Purdue University11th Floor Lecture Hall
3:00 - 3:45pm EDTCoffee/Tea Break11th Floor Collaborative Space 
3:45 - 4:30pm EDTLinear-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

Rüdiger 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