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 setting. In the talk, I will discuss sketching algorithms and lower bounds for Max-DICUT in various space regimes and will briefly touch upon generalizations to arbitrary CSPs. I will conclude with a discussion on open problems in this area.


Video Recording