Seminars

View all Seminars  |  Download ICal for this event

Matroid-convex functions and approximative closure of some polynomial classes.

Series: Bangalore Theory Seminars

Speaker: Rohit Gurjar Indian Institute of Technology Bombay

Date/Time: Dec 23 16:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
Matroid-convex (or M-convex) functions, defined by Murota, are functions on size k subsets of a ground set which satisfy a Steinitzs exchange type inequality. M-convex function minimization can be done by some greedy-type algorithms. More interestingly, Murota proved a splitting theorem that reduces minimization of sum of two M-convex functions to minimizing two M-convex functions separately.

An interesting question in algebraic complexity is to understand approximative closure of various classes of polynomials. We use the above splitting theorem to show that the following class of polynomials is closed under approximation: det(sum_i A_i x_i) where A_is are all rank 1 matrices. That is, any polynomial which can be approximately computed by this model can also be exactly computed by it.

Based on a joint work with Abhranil Chatterjee, Sumanta Ghosh, and Roshan Raj


Speaker Website Link

Microsoft teams link:

Link


Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul