Polynomials over finite fields with applications to Computer Science.

摘要

This work studies multivariate polynomials over finite fields and their applications in computer science. The study of polynomials in computer science is not new. Polynomials have found applications in the areas of algorithm design, cryptography, circuit lower bounds, computational learning and coding theory, to name a few key examples. In this work we continue the research of polynomials in computer science, and focus on four main areas: we study polynomials as a model of computation, where we explore several fundamental problems, such as the relation between exact and approximate computation, the resources required to generate hard functions, and the importance of the base field; we study distributions which are pseudorandom for polynomials, and provide as applications lower bounds for bounded depth circuits; we study coding theoretic questions related to codes arising from polynomials, such as Reed-Muller and BCH codes; and we study property testing for polynomials, which is motivated by recent advances in additive combinatorics. In all these areas, we establish new results which emerge from an improved understanding of the fundamental properties of polynomials over finite fields.