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][1]). Recently, [Kuperberg, Lovett and Peled][2] 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.

  [1]: http://arxiv.org/pdf/1201.4960v2.pdf
  [2]: http://arxiv.org/pdf/1302.4295.pdf