Please note: This distinguished lecture will take place in DC 1302 and online.
Nitin Saxena, N. Rama Rao Chair Professor
Department of Computer Science and Engineering
IIT Kanpur
Border (or approximative) complexity of polynomials plays an integral role in algebraic algorithms and the geometric complexity theory approach to P!=NP. This raises an important open question: can a border circuit be efficiently debordered (i.e., convert from approximative to exact)? Or, could the approximation involve exponential-precision which may not be efficiently simulable? It’s unclear how such circuits can be presented in practice if at all. We will discuss our new presentable-border definition and its application in circuit factorization.
Kumar (ToCT’20) proved the universal power of the border of top-fanin-2 depth-3 circuits. We recently solved some of the related open questions. If time permits, the talk will outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy — it can be computed by a polynomial-size algebraic branching program (ABP).
Based on the works with C.S. Bhargav, Prateek Dwivedi and Pranjal Dutta; (CCC 2021) + (FOCS 2021, invited to SICOMP) + (FOCS 2022) + (STOC 2024).
For more information, visit Nitin Saxena’s website.
Biography
Profession: Nitin was born in 1981, and brought up in Prayagraj, UP, India. He did his BTech CSE at IIT Kanpur (1998–2002). He worked on computational complexity/algebra/number theory in his PhD (2002–06) in IIT Kanpur under Manindra Agrawal. In this period he traveled world over, in particular, a year-long research visit each in Princeton University (2003–04) and National University of Singapore (2004–05).
Nitin joined CWI Amsterdam, The Netherlands as a Scientific Researcher (2006–08). Later, he moved to Hausdorff Center for Mathematics (HCM) in University of Bonn, Germany with a faculty position (2008–13). In 2013, Nitin joined as Associate Professor in CSE, IIT Kanpur, where he was promoted to Professor (2018–) and N. Rama Rao Chair (2019–) positions. He is an Adjunct Faculty in Chennai Mathematics Institute (2018–). He is a founding Coordinator of the Center for Developing Intelligent Systems (CDIS) — a new entity to solve governance problems at scale.
Research: The area of algebraic complexity has seen an intense revival in the last three decades. Many famous open problems in this area have been solved by Nitin in his co-authored papers in the last two decades, inventing highly technical algorithmic-algebra tools. He leads globally in an astonishingly wide area with contributions in primality testing, blackbox PIT (polynomial identity testing, or its famous cousin, the VP≠VNP question), border-complexity analyses in GCT (geometric complexity theory), algebraic dependence, factor-/root-finding (in diverse rings), computing famous topological invariants like the Igusa local-zeta function (via Galois rings) and the Hasse-Weil zeta function (via Galois fields).
Activities: Nitin is a proactive member of the scientific, academic community and contributes to the institute, national, and international committees and policy-making. He chaired the UGRC (Undergraduate Review Committee) to design a modern curriculum for the decade of 2020–30; its key features were reported by the national media. He co-founded the Center for Developing Intelligent Systems to solve local problems at scale.
Nitin is a Member of the (founding) Editorial Board of the journal TheoretiCS. He chaired the premier CS Conference in India — FSTTCS’20 (Track A). He has served in the Program Committees of STOC’24, ISSAC’23, CCC’22, ITCS’22, FOCS’19, FCT’19, FSTTCS’18, STACS’14, CSR’11, CCC’11. He has mentored 16 PhD and 25 Master’s students, and has taught more than 21 courses, 8 of which are now MooC (massive open online courses) on Swayam. He has given 75+ invited talks in inter/national venues.
Awards: IITK Distinguished Alumnus Award (2003), MIT Global Indus Technovators Award (2003), IBM Outstanding PhD Award (2005), Gödel Prize (2006), Fulkerson Prize (2006), INSA Young Scientist Medal, DST Swarna Jayanti Fellow (2015); Shanti Swarup Bhatnagar Prize (2018); N. Rama Rao Chair (2019); IIT Bombay International Award (2023); J.C. Bose Fellowship (2023); Fellow of all Indian Academies: FASc, FNASc (2021), FNAE (2022), FNA (2023).
In 2022, DST & Ministry of Science & Technology profiled him in the top scientists “shaping today’s India.” His papers won the Best Paper (Track A) at the flagship ICALP’11 conference, Best Paper & Best Student Paper Awards at the IEEE Conference on Computational Complexity CCC’06, and Best Student Paper Award at MFCS’22.