We learn from our alumni in this interaction series, often technically, sometimes semi-technically.

C Ramya IMSc, Chennai

C Ramya is currently a faculty member at the Institute of Mathematical Sciences (IMSc), Chennai, INDIA. Prior to this, she was an assistant professor at the Chennai Mathematical Institute, Chennai, INDIA. She was a postdoctoral fellow in the School of Technology and Computer Science (STCS) at the Tata Institute of Fundamental Research (TIFR), Mumbai hosted by Ramprasad Saptharishi. Ramya obtained her Ph.D. under the guidance of B.V.Raghavendra Rao from Indian Institute of Technology, Madras. As part of the dual degree programme, she also received a masters degree in Computer Science and Engineering from Indian Institute of Technology, Madras. Her research is centered around the area of Computational Complexity, which aims at understanding the inherent limitations of computing and the intrinsic hardness of certain computational problems. She is particularly interested in Algebraic Complexity Theory, the study of computation of polynomials. More generally, she is interested in problems with an algebraic or combinatorial flavor and in the inextricable intertwining of Algorithms and Complexity Theory.

In the quest for solving real-world problems, obtaining algorithms that are efficient in terms of computational resources such as time, space, randomness, communication etc., are of vital importance. In this talk, we will be interested in multiple facets of algebraic computation. We will begin by understanding computation of multivariate polynomials by arithmetic circuits and review four decades of progress made towards settling Valiant’s conjecture(the algebraic analogue of P vs. NP problem). Most known works in this regard can be unified under the framework of algebraically natural proofs. While some believe that this framework cannot be extended to settle the truth of Valiant’s conjecture, some of our recent results highlight the existence of natural lower bound techniques for proving circuit size lower bounds against certain rich subclasses of arithmetic circuits. In the second part of the talk, we will view algebraic computation via an algorithmic lens. In particular, we discuss the well-known computational problems of Polynomial(resp., Rational) Identity Testing problem and its potential connections to proving arithmetic circuit size lower bounds.

Organizers