Suppose we have access to $n$ empirical observations of two random variables X,Y and we want to know - are X,Y independent?

In a graph, we call a vertex well-mixing if the standard random walk starting from that vertex reaches close to its stationary distribution fast (say within 'polylogarithmic in the size of the vertex set' steps).

In this talk we will describe some of our recent work giving new upper and lower bounds on the approximability of constraint satisfaction problems (CSPs) in the streaming and sketching settings.

Abstract: Given an edge weighted graph and a spanning tree, $T$, the {\em tree augmentation problem} is to pick a minimum weight set of edges, $F$, such that $T\cup F$ is 2-edge connected. Williamson et.al.

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.