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

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
UChicago CS News

In-Fridge Controller Could Scale Up Quantum Computers, Award-Winning UChicago Research Finds

Jan 10, 2022
UChicago CS News

EPiQC Research Receives Best Paper Award at IEEE Quantum Week

Oct 22, 2021
UChicago CS News

UChicago and EPiQC Alum Yongshan Ding Joins Yale in Faculty Position

Oct 08, 2021
UChicago CS News

UChicago Researchers Excel in IBM Quantum Open Science Challenge

Jul 30, 2021
UChicago CS News

Largest-Ever DSI Summer Lab Adds 55 Students, New Social Impact Track

Jul 13, 2021
UChicago CS News

First-Ever Data4All Workshop Nurtures Future Data Scientists From Chicago’s South Side

Jun 21, 2021
UChicago CS News

Two UChicago CS PhD Students Receive 2021 Harper Fellowship

Jun 07, 2021
UChicago CS News

Three EPiQC Papers Chosen By IEEE Micro for Annual Top Picks Awards

May 27, 2021
UChicago CS News

Victor Veitch, New UChicago Data Science Faculty, Builds “Safe and Credible” AI Systems

Apr 27, 2021
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