#### 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.

Done