The Taub Faculty of Computer Science Events and Talks

We study complexity measures of Boolean functions on the symmetric group and other domains. This generalizes classical work on functions over the Boolean cube. Additionally, we construct efficient circuits for low sensitivity functions. Using our theory we give an alternate proof for the characterization of extremal t-setwise-intersecting families of permutations. Joint work with Yuval Filmus, Noam Lifshitz, Nathan Lindzey and Marc Vinyals