The multiplicity Schwartz-Zippel lemma provides a bound on the total multiplicity of zeroes of a low-degree polynomial within a product set. It implies that multiplicity codes, which can be thought of as generalizations of Reed-Muller codes that consist of evaluations of derivatives along with the evaluations of the polynomial - have good distance. There has been progress towards the problem of algorithmizing this lemma - that is, unique decoding to find the closest codeword given a possibly corrupted received word - for certain cases such as the product set being a vector space, or the number of derivatives given being large. In this project, we describe an algorithm for the multiplicity Schwartz-Zippel lemma for general product sets and any number of derivatives. For the purposes of this project, we restrict ourselves to the bivariate case. Our algorithm is motivated by Kim and Kopparty’s algorithm for decoding Reed-Muller codes over product sets. In the process of adapting it, we develop new notions of weight and distance, as well as a new approach to analysing Forney’s classical algorithm for decoding concatenation codes. The results presented in this work are based on joint work with Siddharth Bhandari, Prahladh Harsha and Mrinal Kumar (IIT Bombay).
