BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//IORA - Institute of Operations Research and Analytics - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:IORA - Institute of Operations Research and Analytics
X-ORIGINAL-URL:https://iora.nus.edu.sg
X-WR-CALDESC:Events for IORA - Institute of Operations Research and Analytics
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Singapore
BEGIN:STANDARD
TZOFFSETFROM:+0800
TZOFFSETTO:+0800
TZNAME:+08
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Singapore:20260227T100000
DTEND;TZID=Asia/Singapore:20260227T113000
DTSTAMP:20260420T193011
CREATED:20260203T030056Z
LAST-MODIFIED:20260203T030156Z
UID:27376-1772186400-1772191800@iora.nus.edu.sg
SUMMARY:DAO-ISEM-IORA Seminar Series: Georgina Hall
DESCRIPTION:Name of Speaker\n\n\nGeorgina Hal\n\n\n\n\nSchedule\n\n\n27 Feb 2026\, 10am – 11.30am \n (60 min talk + 30 min Q&A) \n\n\n\n\nVenue\n\n\nBIZ1 0302\n\n\n\n\nLink to register \n(via Zoom) \n\n\nhttps://nus-sg.zoom.us/meeting/register/MSVeTEDGTSGxi0TGgyLmNg\n\n\n\n\nTitle\n\n\nSum of Squares Submodularity\n\n\n\n\nAbstract\n\n\nWe introduce the notion of t-sum of squares (sos) submodularity\, which is a hierarchy\, indexed by t\, of sufficient algebraic conditions for certifying submodularity of set functions. We show that\, for fixed t\, each level of the hierarchy can be verified via a semidefinite program of size polynomial in n\, the size of the ground set of the set function. This is particularly relevant given existing hardness results around testing whether a set function is submodular (Crama\, 1989). We derive several equivalent algebraic characterizations of t-sos submodularity and identify submodularity-preserving operations that also preserve t-sos submodularity. We further present a complete classification of the cases for which submodularity and t-sos submodularity coincide\, as well as examples of t-sos-submodular functions. We demonstrate the usefulness of t-sos submodularity through three applications: (i) a new convex approach to submodular regression\, involving minimal manual tuning; (ii) a systematic procedure to derive lower bounds on the submodularity ratio in approximate submodular maximization\, and (iii) improved difference-of-submodular decompositions for difference-of-submodular optimization. \nThis is joint work with Anna Deza (Georgia Tech). \n\n\n\n\nAbout the Speaker\n\n\nGeorgina Hall is an Assistant Professor at INSEAD in the Decision Sciences Area. Her research focuses on convex relaxations of NP-hard problems\, particularly those that arise in polynomial optimization and problems on graphs. Prior to joining INSEAD in 2019\, she was a postdoctoral student at INRIA. She completed her PhD in Operations Research and Financial Engineering at Princeton University in 2018. She is the recipient of the 2018 INFORMS Optimization Society Young Researcher’s Prize and the 2020 Information Theory Society Paper Award\, among other awards.
URL:https://iora.nus.edu.sg/events/dao-isem-iora-seminar-series-georgina-hall/
CATEGORIES:IORA Seminar Series
END:VEVENT
END:VCALENDAR