From Query to Sequential Computation: A New Approach

Add to your list(s) Download to your calendar using vCal

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

If you have a question about this talk, please contact Tom Gur.

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

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.