On Superpolynomial Size Matching Vector Families and Polynomial Representations of OR Modulo Composites

Abstract

In this paper we discuss the basic construction yielding a super-polynomial size matching vector family, which have been shown to yield the best known constant-query locally decodeable codes. We exposit the best known lower bound on the degree of a representation of OR and the best upper bound on the size of matching vector families assuming the PFR conjecture. Interestingly, as shown by T. Tao and B. Green, the PFR conjecture is equivalent to a quantitative strengthening of the Gower’s Inverse Theorem for the U3 norm. We discuss this and further properties of nonclassical polynomials. Finally, we conjecture a possible relationship between classical polynomials and nonclassical polynomials as a way to improve the lower bound on the degree of the OR.