Approximation Algorithms for Maximum Directed Cut in Streaming Settings

Approximation algorithms for Maximum Directed Cut in Streaming Settings

Abstract: Given a directed graph, the Maximum Directed Cut (Max-DICUT) problem asks to estimate the size of the largest directed cut, an ordered partition of the vertex set whose size is given by the number of edges from one set to the other. The Max-DICUT problem has emerged as a central problem in the study of Constraint Satisfaction Problems (CSPs) in the streaming model of computation. In the talk, I will discuss our algorithms for Max-DICUT in various settings of the streaming model and will briefly touch upon generalizations to arbitrary CSPs. I will conclude with a discussion of several open problems in this area.

Bio: Santhoshini is a fifth-year computer science graduate student at Harvard University, advised by Prof. Madhu Sudan. She received her dual degree of BTech(Hons.) and MTech in Computer Science from IIT Madras.Broadly interested in the design and analysis of algorithms for combinatorial optimization problems. Mainly studies algorithms in settings where there’s limited access to the input data or uncertainty in it. These include streaming and online settings, and game theory settings where the input to the algorithm is provided by strategic agents.Supported by the Google PhD fellowship. Will be joining TTIC as a Research Assistant Professor in Fall 2023.