Algorithmic Coding Theory
(June 13 - 17, 2016)

Picture
Description

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
  • 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.

Organizing Committee

= speaker    = poster presenter

Monday June 13, 2016
Time Description Speaker Location Abstracts Slides
8:30 - 9:00Registration11th Floor Collaborative Space
9:00 - 9:15WelcomeICERM Director11th Floor Lecture Hall
9:15 - 10:15Maximally recoverable codes (BONUS - Mini-tutorial on storage!)Sergey Yekhanin, Microsoft11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 11:45Robust Positioning PatternsSwastik Kopparty, Rutgers University11th Floor Lecture Hall
PDF
12:00 - 2:00Break for Lunch / Free Time
2:00 - 2:45Capacity Via Symmetry I - a New Proof for an Old CodeMarco Mondelli, Ecole Polytechnique Federale de Lausanne (EPFL)11th Floor Lecture Hall
PDF
PDF
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space
3:45 - 4:30Capacity Via Symmetry II - General Channels and Weight DistributionRudiger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL)11th Floor Lecture Hall
PDF
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

Tuesday June 14, 2016
Time Description Speaker Location Abstracts Slides
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
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 11:45Reliable Communication over Highly Connected Noisy NetworksKlim Efremenko, Tel-Aviv University11th Floor Lecture Hall
PDF
12:00 - 2:00Break for Lunch / Free Time
2:00 - 2:45Towards Optimal Deterministic Coding for Interactive CommunicationNoga Ron-Zewi, IAS11th Floor Lecture Hall
PDF
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space
3:45 - 4:30Constant-rate coding for multiparty interactive communication is impossibleRan Gelles, Princeton University11th Floor Lecture Hall
PDF

Wednesday June 15, 2016
Time Description Speaker Location Abstracts Slides
9:15 - 10:15Tamper Detection and Non-malleable codes (BONUS - Mini-tutorial on non-malleable codes!)Daniel Wichs, Northeastern University11th Floor Lecture Hall
PDF
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
PDF
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 theoryErdal Arikan, Bilkent University11th Floor Lecture Hall
PDF
PDF

Thursday June 16, 2016
Time Description Speaker Location Abstracts Slides
9:15 - 10:15List-decoding for rank-metric codes (BONUS - Mini-tutorial on list-decoding!)Carol Wang, Carnegie Mellon University11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 11:45Dual Channels and Dual Codes- Using Heisenberg uncertainty to achieve Shannon capacityJoseph Renes, ETH Zurich11th Floor Lecture Hall
PDF
12:00 - 2:00Break for Lunch / Free Time
2:00 - 2:45Recent progress on codes for worst-case deletionsVenkat Guruswami, Carnegie Mellon University11th Floor Lecture Hall
PDF
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space
3:45 - 4:30Explicit Two-Source Extractors and Resilient FunctionsDavid Zuckerman, University of Texas11th Floor Lecture Hall
PDF

Friday June 17, 2016
Time Description Speaker Location Abstracts Slides
9:15 - 10:15Polar Coding (BONUS - Mini-tutorial on polar codes)Erdal Arikan, Bilkent University11th Floor Lecture Hall
PDF
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 11:45On the Finite Length Scaling of q -ary Polar CodesDina Goldin, Tel Aviv University11th Floor Lecture Hall
PDF
12:00 - 2:00Break for Lunch / Free Time
2:00 - 2:45NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott ProblemElena Grigorescu, Purdue University11th Floor Lecture Hall
PDF
3:00 - 3:45Coffee/Tea Break11th Floor Collaborative Space
3:45 - 4:30Linear-time list recovery of high-rate expander codesBrett Hemenway, University of Pennsylvania11th Floor Lecture Hall
PDF
PDF