<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"><meta http-equiv="content-type" content="text/html; charset=utf-8"><span style="-webkit-text-size-adjust: auto;">Departments of Mathematics & Computer Science</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Combinatorics & Theory Seminar</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Tuesday, May 31, 3:30pm</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Location <b>Crerar 298 </b>(note a different room!)</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Anup Rao (University of Washington)</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">TITLE: </span>A Fourier Analytic Criterion for Decoding on the BSC<br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">ABSTRACT: </span><span style="font-family: Arial, sans-serif; white-space: pre-wrap; -webkit-text-size-adjust: auto;">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.</span><div style="-webkit-text-size-adjust: auto; font-family: Arial, sans-serif; white-space: pre-wrap;"><p><u></u></p></div><div style="-webkit-text-size-adjust: auto; font-family: Arial, sans-serif; white-space: pre-wrap;"><p>1. We give a tight bound on the weight distribution of every transitive linear code C ⊆ FN2 : Prc∈C[|c| = αN]<wbr> ≤ 2−(1−h(α))·d<wbr>im(C).<u></u><u></u></p><p>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<wbr>)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.<u></u><u></u></p><p>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. <u></u><u></u></p><p>Joint work with Oscar Sprumont.</p></div></div></body></html>