Intractability of min- and max-cut in streaming graphs

► A minimum/maximum cut cannot be computed exactly by a one-pass streaming algorithm. ► This holds for deterministic and randomized algorithms. ► Tools of communication complexity are utilized.