[Colloquium] CS Theory Seminar - Anup Rao, Tuesday, May 31, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO

COMPUTER SCIENCE DEPARTMENT

PRESENTS



Anup Rao
University of Washington

 [A picture containing person, person, indoor, male  Description automatically generated]


Tuesday, May 31, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107


“A Fourier Analytic Criterion for Decoding on the BSC”

 Abstract:  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




--
Jose J Fragoso
Project Assistant IV
Computer Science Department
5730 S. Ellis – Room 200C
Chicago, IL. 60637
jfragoso at uchicago.edu
(773) 702-6614
(773) 702-8487 FAX

[signature_1572818061]



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220523/bfc5a980/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 46165 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220523/bfc5a980/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 459593 bytes
Desc: image003.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220523/bfc5a980/attachment-0001.png>