Polynomails and computation
Jaikumar Radhakrishnan, Tata Institute of Fundamental Research
Abstract: Over the past three decades several connections between algebra and computing have been discovered. The two most important reasons for this are: (1) several naturally occurring problems in science and engineering are inherently algebraic, (2) algebra can be exploited in the design of computer systems, most notably, because of its central role in coding theory. We will illustrate through examples these two aspects of the role of algebra in computation.
First, using the fundamental operation of matrix multiplication describe how algebraic algorithms arise in computation. We will then present Valiant's result from the 1970s showing that the problem of recognizing sentences in certain formal languages can be solved using matrix multiplication. Next, we present an overview of coding theory, stating its goals and challenges. We then describe an error-correcting code obtained from algebra using polynomials, and briefly list their properties and the success in developing decoding algorithms for them.
The aim of coding theory is generally to obtain deterministic behavior even in the presence of, sometimes malicious, randomness or noise. However, the ideas developed by coding theorists can be turned around to better understand the role of randomness in computing. In recent works, polynomials and codes have been exploited to generate pseudorandomness and derandomize randomized algorithms. The algebraic ideas underlying these developments will be the subject of the remaining talks. We will set up the framework, with the aim of providing the context for the other talks in the session.