BARC talk by Sagnik Mukhopadhyay

Tuesday, 23 November 2021, Sagnik Mukhopadhyay, Postdoc recently transferred to DIKU and hostet by Danupon Nanongkai, will give a talk on "A(n almost) Universal Algorithm for Global Minimum Cut".

Title: 
A(n almost) Universal Algorithm for Global Minimum Cut

Abstract:
Consider the following 2-respecting min-cut problem: Given a weighted graph G and its spanning tree T, find the minimum cut among the cuts that contain at most two edges in T. This problem is an important subroutine in Karger's celebrated randomized near-linear-time min-cut algorithm [STOC'96]. I will present a new approach for this problem which can be implemented in many settings, such as sequential, cut-query, streaming, PRAM, distributed CONGEST, and 2-party communication protocol, achieving the state of the art in most cases.

In this talk, Sagnik will focus on the cut-query and communication setting. This is a culmination of three papers with co-authors Danupon Nanongkai, Yuval Efron, Michal Dory, and Andrés Lopez Martinez.

Bio:
Sagnik Mukhopadhyay is currently a post-doctoral researcher at the Department of Computer Science at the University of Copenhagen. His host is Danupon Nanongkai. In his previous avatar, he was a researcher at KTH Royal Institute of Technology during 2019-2021, a post-doctoral fellow at IUUK, Charles University, hosted by Michal Koucký in 2018, in the APC group at KTH Royal Institute of Technology during 2017-2018, and a graduate student in theoretical computer science at TIFR Mumbai until August 2017, working under the supervision of Dr. Arkadev Chattopadhyay. Sagnik's research interest lies broadly in graph algorithms and complexity theory, specifically in communication complexity.