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