Computer Science/Discrete Mathematics Seminar I

The degree mantra states that any non-zero univariate polynomial of degree at most d has at most d roots (counted with multiplicity). A generalization of this to the multivariate setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over any field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set.

In this talk, I'll present two recent results which algorithmize the above lemma under different settings of parameters.

(a) we show how to decode (even list-decode) multivariate multiplicity codes of large multiplicities in polynomial time over arbitrary finite product sets (over fields of large characteristic and zero characteristic).

(b) we give an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields provided the multiplicity parameter is small.

Previously, such algorithms were known only when the arbitrary product sets had some special algebraic structure.

Based on joint work with S. Bhandari, M. Kumar, A. Shankar and M. Sudan