We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = \cdots = \mathcal{C}(x_L)$. The associated complexity classes Polynomial Multi-Pigeonhole Principle ($(A,B)$-$\rm{PMPP}^L$) consist of all problems that reduce to this problem.
We show close connections between $(A,B)$-$\rm{PMPP}^L$ and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding distinct codewords or lattice points that lie in a certain small ball) are in $(A,B)$-$\rm{PMPP}^L$, with a more-or-less smooth tradeoff between the distance and the parameters $A$, $B$, and $L$. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that some bounds on the minimum distance are actually complete for these classes (for codes represented by arbitrary circuits).
We go on to study $(A,B)$-$\rm{PMPP}^L$ as an interesting family of complexity classes in their own right, and we uncover a rich structure. We first show that techniques that were recently developed in the cryptographic literature on multicollision-resistant hash functions can be applied in our setting. Specifically, we show inclusions of the form $(A,B)\text{-}\rm{PMPP}^L \subseteq (A',B')\text{-}\rm{PMPP}^{L'}$ for certain non-trivial parameters, black-box separations between such classes in different parameter regimes, and a non-black-box proof that $(A,B)\text{-}\rm{PMPP}^{L} \in \rm{FP}$ if $(A',B')\text{-}\rm{PMPP}^{L'} \in \rm{FP}$ for yet another parameter regime. We also show that $(A,B)$-$\rm{PMPP}^L$ lies in the recently introduced complexity class Polynomial Long Choice for some parameters.
