|
In this work, we consider permutation-symmetric tilings. We show that in this case the answer is $\Theta(n/\sqrt{\log n})$.
Our work is motivated by the study of strong versions of the parallel repetition theorem, which if true would have significant applications. Unfortunately, strong parallel repetition fails in general [Raz]. Our result suggests there may be important special cases where it still applies.
Joint work with Mark Braverman.