Improved Streaming Algorithms for Max-DICUT via Local Snapshots

Explore advanced streaming algorithms for the Maximum Directed Cut (Max-DICUT) problem in this 45-minute lecture by Santhoshini Velusamy from Toyota Technological Institute at Chicago. Delve into the challenge of estimating the largest directed cut in a given graph and its significance in studying Constraint Satisfaction Problems (CSPs) in streaming settings. Learn about the current 4/9 approximation achieved through log space algorithms and discover more sophisticated approaches that surpass this limit using o(n) space. Examine the concept of local graph snapshots and their role in improving Max-DICUT approximations. Gain insights from joint research with Raghuvansh Saxena, Noah Singer, and Madhu Sudan, presented as part of the Sublinear Graph Simplification series at the Simons Institute.

Improved streaming algorithms for Max-DICUT via local snapshots