BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221223T120000Z
UID:c57a0de88bf4a8b12dce774334109baf-381
DTSTAMP:19700101T120016Z
DESCRIPTION:Matroid-convex functions and approximative closure of some polynomial classes.
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/381/matroid-convex-functions-and-approximative-closure-of-some-polynomial-classes/
SUMMARY: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	https://www.cse.iitb.ac.in/~rgurjar/

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul
DTSTART:20221223T120000Z
END:VEVENT
END:VCALENDAR