A family of permutations $T \subseteq S_n$ is called a $t$-wise permutation if its action on any $t$-tuple of elements is uniform. In other words, for any distinct elements $i_1, \cdots, i_t \in [n]$ and distinct elements $j_1, \cdots, j_t \in [n]$, $$ |\{ \pi ∈ T : \pi(i_1) = j_1, \cdots, \pi(i_t) = j_t \} | = \frac{1}{n(n − 1)· · ·(n − t + 1)}|T|.$$
In particular, for fixed $t$, $|T|$ must be of size at least $\sim n^t$. For $t \ge 4$, the only known construction of a $t$-wise permutation is of size $t^{2n}$ (see this elementary work by Finucane, Peled, and Yaari). Recently, Kuperberg, Lovett and Peled have proved the following strong result:
For all integers $n \ge 1$ and $1 \le t \le n$ there exists a $t$-wise permutation $T \subset S_n$ satisfying $|T| ≤ (cn)^{ct}$ for some universal constant $c > 0$.
Their proof is probabilistic, and involves a careful study of a carefully constructed random walk. Their paper contains other examples, such as designs and orthogonal arrays.
As far as I understand, having a constructive such family of permutations (or other structures described in the paper) can be applied in turning randomized algorithms into deterministic algorithms.