BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:From Query to Sequential Computation: A New Approach - Sagnik Mukh
 opadhyay (Sheffield)
DTSTART:20240611T130000Z
DTEND:20240611T140000Z
UID:TALK213664@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Submodular function minimisation (SFM) is an important class o
 f optimisation problems that encompasses several classical optimisation pr
 oblems such as graph cuts/flows\, matroid intersection\, to name a few. Th
 e standard model for studying SFM is through the lens of evaluation query.
  However\, for all of its classical instantiations\, we are usually more i
 nterested in the sequential (unit-cost RAM) complexity. Hence. an importan
 t aspect of designing fast sequential algorithms is to find an efficient i
 mplementation of the evaluation oracle---this is almost non-existent for f
 ine-grained time complexities\, such as nearly linear or sub-quadratic tim
 e.\n\nInspired by fully persistent data structures\, I will introduce a ne
 w 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 sequ
 ential world. I will showcase its efficacy in the context of matroid inter
 section and global minimum cut---two central problems in the gamut of SFM.
 \n\nThis talk will contain some published work (with co-authors Danupon\, 
 Joakim\, Ta-Wei\, STOC 2023) and some unpublished work (with my PhD studen
 t at UoB\, Shravan).
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR