Polynomials, Divided Differences, And Codes

Polynomial codes are algebraic error-correcting codes with widespread applications in TCS and allied areas. Due to their good rate vs distance tradeoff, as well as amenability to a plethora of algebraic techniques, an important line of enquiry is to understand their decodability properties under different paradigms.

Some of the best explicit polynomial code constructions have been achieved via a folding trick, realized in multiple ways, one of which is by using the classical derivative operator on polynomials. This opens an avenue for instantiating the polynomial method 'extended with multiplicities' in the analysis of such codes. In some cases, a successful a analysis might necessarily be sensitive to the characteristic of the underlying field.

In this talk, we will introduce an alternate, equally classical notion of derivative into the polynomial method, and see that this allows for characteristic insensitive constructions. We will see applications towards both efficient list decoding, and hardness of decoding.