Quadratic polynomials of small modulus cannot represent OR

Holden Lee

An open problem in complexity theory is to find the minimal degree of a polynomial representing the $n$-bit OR function modulo composite $m$. This problem is related to understandi…