Date & Time:
May 31, 2022 3:30 pm – 4:30 pm
Crerar 298, 5730 S. Ellis Ave., Chicago, IL,
05/31/2022 03:30 PM 05/31/2022 04:30 PM America/Chicago Anup Rao (U. of Washington) – A Fourier Analytic Criterion for Decoding on the BSC CS Theory Seminar Crerar 298, 5730 S. Ellis Ave., Chicago, IL,

We present an approach to showing that a linear code is resilient to random errors. We then use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.

1. We give a tight bound on the weight distribution of every transitive linear code C ⊆ FN2 : Prc∈C[|c| = αN] ≤ 2−(1−h(α))·dim(C).

2. We give a Fourier analytic criterion that certifies that a linear code C can be decoded on the binary symmetric channel. Let Lw(x) denote the level function that is 1 if |x| = w and 0 otherwise, and let C⊥ denote the dual code of C. We show that bounds on Ec∈C⊥[LˆεN(c)2] imply that C recovers from errors on the binary symmetric channel with parameter ε. Weaker bounds can be used to obtain list-decoding results using similar methods.

3. Motivated by the above results, we use complex analysis to give tight estimates for the Fourier coefficients of the level function. We then combine these estimates with our weight distribution bound to give list-decoding results for transitive linear codes and Reed-Muller codes.

Joint work with Oscar Sprumont.

Bio: Anup Rao is a professor of computer science at the Paul G. Allen School of Computing at the University of Washington.

Host: Aaron Potechin


Related News & Events

Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube