Alladi Ramakrishnan Hall

Recent Trends in Arithmetic Complexity

Anuj Tawari

IMSc

How complex can a given multivariate polynomial be? Can every polynomial which can be easily described be also computed efficiently? This problem, also known as the VP vs VNP problem, has attracted a lot of attention and tremendous progress has been made, particularly, in the last couple of years. This thesis explores some of this recent development.

(MSc seminar)