Please note: This seminar will take place in DC 1304 and online.
Swastik Kopparty, Professor
Department of Mathematics and Department of Computer Science
University of Toronto
Let F be a finite field and let chi be an additive or multiplicative character of F of order 2. We give a polynomial time algorithm to recover a low degree polynomial g(X) over F, given the values of chi(g(b)), for each b in F, even if a constant fraction of these values have errors.
For multiplicative characters this was previously unknown even for the case of no errors. For additive characters this gives an efficient algorithm for decoding dual-BCH codes. The algorithms use ideas from Stepanov's polynomial-method proof of the classical Weil bounds on character sums, as well as from the Berlekamp-Welch decoding algorithm for Reed-Solomon codes. Our result can be viewed as an algorithmic version of the Weil bound.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.