Room 327

The Tau Conjecture and Arithmetic Circuit Lower Bounds

N.P. Swaroop

IMSc

Algebraic Complexity was proposed by Valiant in order to understand the
complexity of computing polynomials. Using arithmetic circuits as the
model of computation, we seek to understand which polynomials have small
sized circuits and which ones do not. In this framework, VP is the class of polynomials with small sized circuits (analogue of P in the
boolean world), whereas
VNP is the class of polynomials which can be written as a sum over
polynomials in VP (in some sense, analogue of NP). The most important problem in Algebraic Complexity is to separate the classes VP and
VNP. One way to do this is to show a super polynomial lower bound on the size of the arithmetic circuit computing the permanent
polynomial. Some conditional lower bounds are known, e.g., based on the
Tau-conjecture of Shub and Smale. The conjecture states that the number of integer roots of an integer polynomial is polynomially upper
bounded in terms of the
size of the smallest arithmetic circuit computing the polynomial. In this thesis, we will
see the relevance of the Tau-conjecture and some of its modifications in deriving lower bounds in Algebraic Complexity theory.