Tata Institute of Fundamental Research

Determinantal complexity of the power sum polynomial

STCS Student Seminar
Speaker: Varun Ramanathan
Date: Friday, 3 Mar 2023, 16:30 to 17:30
Venue: A201

(Scan to add to calendar)
Abstract:  We will introduce the notion of determinantal complexity, one of the main characters in the VP vs VNP question, which is the algebraic analogue of the P vs NP question. We will focus on a specific polynomial - the power sum polynomial - and see proof sketches for an upper bound and a lower bound on its determinantal complexity. The lower bound will be from a paper by Alper, Bogart and Velasco. Prerequisites for the talk are basic linear algebra (rank, etc) and basic calculus (partial derivatives, chain rule, etc). There will be some usage of tools from algebraic geometry but we won't see their proofs.