More power by using fewer permutations

It is conventionally believed that permutation-based testing methods should ideally use all permutations. We challenge this by showing that we can sometimes obtain dramatically more power by using a tiny subgroup. As the subgroup is tiny, this also comes at a much lower computational cost. Moreover, the method remains valid for the same hypotheses. We exploit this to improve the popular permutation-based Westfall and Young MaxT multiple testing method. We analyse the relative efficiency in a Gaussian location model, and find the largest gain in high dimensions.