[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, May 31, 3:30pm
Location Crerar 298 (note a different room!)

Anup Rao (University of Washington)

TITLE: 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.