Abstract

Submodular function minimisation (SFM) is an important class of optimisation problems that encompasses several classical optimisation problems such as graph cuts/flows, matroid intersection, to name a few. The standard model for studying SFM is through the lens of evaluation query. However, for all of its classical instantiations, we are usually more interested in the sequential (unit-cost RAM ) complexity. Hence. an important aspect of designing fast sequential algorithms is to find an efficient implementation of the evaluation oracle—-this is almost non-existent for fine-grained time complexities, such as nearly linear or sub-quadratic time.

Inspired by fully persistent data structures, I will introduce a new data structure-friendly query model, denoted as the dynamic query, in the context of SFM . The goal of introducing such a query model is to have an easy transfer of techniques from the evaluation query world to the sequential world. I will showcase its efficacy in the context of matroid intersection and global minimum cut—-two central problems in the gamut of SFM .

This talk will contain some published work (with co-authors Danupon, Joakim, Ta-Wei, STOC 2023 ) and some unpublished work (with my PhD student at UoB, Shravan).