skip to content

Department of Computer Science and Technology

Tuesday, 11 June, 2024 - 14:00 to 15:00
Sagnik Mukhopadhyay (Sheffield)
Computer Laboratory, William Gates Building, Room SS03

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).

Seminar series: 
Algorithms and Complexity Seminar

Upcoming seminars