The story of set disjointness
The satisfiability problem has emerged as the queen of the complexity zoo. She is the quintessential NP-complete hard-to-find but easy-to-recognize search problem in computer science. There are hundreds if not thousands of problems that are now known to be equivalent to SAT, and our rich theory of complexity classes is centered around its queen. In the world of communication complexity, the set disjointness problem has similarly emerged as the quintessential hard-to-find but easy-to-recognize problem. There is an impressive collection of problems in many diverse areas whose hardness boils down to the hardness of the set disjointness problem in some model of communication complexity. Moreover, we will argue that proving lower bounds for the set disjointness function in a particular communication