Skip to content. | Skip to navigation

Personal tools

Theme for TIFR Centre For Applicable Mathematics, Bangalore

Navigation

You are here: Home / Events / Closure of algebraic complexity classes under factoring.

Closure of algebraic complexity classes under factoring.

Nitin Saxena (IIT-Kanpur)
Speaker
Nitin Saxena (IIT-Kanpur)
When Aug 05, 2024
from 02:00 PM to 04:00 PM
Where LH-111, First Floor (Hybrid)
Add event to calendar vCal
iCal

RUNAWAY SEMINAR

Title: Closure of algebraic complexity classes under factoring.

Abstract: Polynomial factoring is one of the most fundamental problems in the area of computational algebra. Its variants have attracted a huge amount of attention in the last half-a-century. On the other hand, algebraic complexity theory classifies polynomials, into complexity classes, according to computational resources. Could we show that these classes afford polynomial factoring algorithms?
In this talk we will focus on four algebraic complexity classes--- size-s circuits VP_{nb}, size-s degree-s circuits VP, size-s degree-s verifier circuits VNP, and size-s algebraic branching programs VBP. We will discuss the algebraic methods, inspired from analysis, that have been developed to do factoring in these complexity classes. We will list the open questions and make some related conjectures.
  
[This is based on the joint work with Pranjal Dutta, Amit Sinhababu (J.ACM'22, STOC'18), and the follow-up papers by others.] [https://www.cse.iitk.ac.in/users/nitin/research.html]

Meeting ID: 984 0519 1052
Filed under: