![](/sites/default/files/styles/workshop_banner_sm_1x/public/logo_for_data_structures_and_optimization_for_fast_algorithms_.png.jpg?itok=uePdFHVY)
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).