| Title | : | Singularity Testing and Symbolic Determinant |
| Speaker | : | Dr. Abhranil Chatterjee (INSPIRE faculty @ ISI, Kolkata) |
| Details | : | Tue, 9 Jul, 2024 2:00 PM @ SSB 334 |
| Abstract: | : | Algebraic complexity is a sub-area of computational complexity that aims to study the efficient computation of multivariate polynomials. In this talk, I will discuss my research work and some of the recent progress in algebraic complexity. Derandomization of the polynomial identity testing (PIT) problem is an intriguing open problem in theoretical computer science. An (almost) equivalent formulation of the PIT problem is the singularity testing of a symbolic matrix, also known as the symbolic determinant identity testing. Interestingly, the noncommutative counterpart of this problem admits a deterministic polynomial-time white-box algorithm. A randomized polynomial-time algorithm is known for this problem in the black-box setting. I will discuss my recent work where we obtain a deterministic polynomial-time algorithm for the singularity testing problem in the partially commutative setting. This non-trivial generalization also yields the first deterministic polynomial-time algorithm for the equivalence testing of weighted multi-tape automata for constant many tapes solving a long-standing open problem. Rational identity testing (RIT) is a closely related problem. It asks whether a noncommutative rational formula (formula with additions, multiplications and inverses) has a nonzero matrix evaluation of any dimension. Designing an efficient black-box algorithm for these problems was a significant open problem. I will then discuss my recent work that shows the first quasipolynomial-size hitting set construction for all rational formulas of polynomial size. The construction also yields a deterministic quasi-NC upper bound for RIT. |
