Room 327

Algebraic Models of Computation

Nitin Saurabh

IMSc

(MSc thesis seminar)

In 1979, Valiant had proposed an analogue of the theory of NP-completeness in an entirely algebraic framework to study the complexity of polynomial families. Artihmetic circuits form the most standard model for studying the complexity of polynomial computations. In a later note in 1992, Valiant argued that in order to prove lower bounds for boolean circuits, obtaining lower bounds for arithmetic circuits should be a first step. One could hope that techniques from well-developed areas of mathematics may help us to solve fundamental problems in algebraic complexity theory. Therefore, it has attracted a large amount of research in last two decades. As a consequence, there has been a lot of progress in the area.

The aim of this thesis is to explore Valiant's approach and to understand different models of algebraic computation. In the process, we survey known results and newer techniques. We discuss simple combinatorial proofs of known results like VNP = VNP$_e$ and study combinatorial characterization of classes VP and VQP. Further, we explore the parallelization of the class VP and discuss a complete problem for the same class. We also cover classical proof of completeness for the permanent family. Later, we study how the complexity of computing certain integers is related to separating constant-free algebraic classes.