Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-018 | 28th January 2024 01:09

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices


Authors: Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
Publication: 28th January 2024 15:14
Downloads: 211


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.

ISSN 1433-8092 | Imprint