Decoding multivariate multiplicity codes on product sets

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set.

Authors

• Siddharth Bhandari
• Prahladh Harsha
• Mrinal Kumar 0001
• Madhu Sudan 0001

Keywords

• Schwartz-Zippel lemma
• list decoding
• multiplicity codes