Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Coding Theory: Syndrome Decoding of Reed-Muller Codes and Tensor Decomposition over Finite Fields
event speaker icon
Aditya Potukuchi (Rutgers University)
event date icon
Sunday, 30.06.2019, 14:30
event location icon
Room 601 Taub Bld.
In this talk, we will look at decoding Reed-Muller codes beyond their minimum distance when the errors are random (i.e., in the binary symmetric channel). A beautiful result of Saptharishi, Shpilka and Volk showed that for binary Reed-Muller codes of length n and degree n - O(1), one can correct polylog(n) random errors in poly(n) time (which is well beyond the worst-case error tolerance of O(1)). We give two new algorithms for this problem, both of which show that the previous error-correction can even be done in one-pass using only polylog(n) space:

1. The first is via. a connection to the well-studied `tensor decomposition problem' in the machine learning world.
2. The second via a reduction to finding all common roots of a space of low degree polynomials, which is of independent interest.

Joint work with Swastik Kopparty.