Abstract
I will talk about a quantum sketch for a set S ⊆ U that answers the following question: given a partition of U into pairs, how many of these pairs are in S? Originating in communication complexity, where a similar sketch was used to prove exponential advantage in one-way communication, this sketch can be used to construct space-efficient algorithms for graph problems, such as triangle counting (with polynomial space advantage over classical algorithms) and Max-Dicut (with exponential advantage).