| Title | : | Exploring multiple facets of algebraic computation |
| Speaker | : | Dr. C Ramya (Faculty member, Institute of Mathematical Sciences (IMSc), Chennai) |
| Details | : | Thu, 21 Sep, 2023 4:00 PM @ CS25 |
| Abstract: | : | 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. |
