We present analysis of time-space tradeoffs for both the search and decision variants of the k-collision problem in algorithmic perspective, where \(k \in \left[ 2, O(\operatorname {polylog}(N))\right] \) and the underlying function is \(f_{N,M} : [N] \rightarrow [M]\) with \(M \ge N\) . In contrast to prior work that focuses either on 2-collisions or on random functions with \(M = N\) , our results apply to both random and arbitrary functions and extend to a broader range of k. The tradeoffs are derived from explicit algorithmic constructions developed in this work, especially for decision problems when \(k\ge 3\) . For 2-collision problems, we show that for any random function \(f_{N,M}\) with \(M \ge N\) , the time-space tradeoff for finding all 2-collisions follows a single curve \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}}\right) }\) , where T denotes time complexity and S denotes available space. This tradeoff also extends to arbitrary functions with at most O(N) total 2-collisions. For 3-collision problems, we identify two time-space tradeoff curves for the search variant over random functions, depending on the available space S. For arbitrary functions, we show that the decision problem can be solved with a tradeoff of \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_3}\right) }\) , where \(n_{i}\) denotes the number of i-collisions. Surprisingly, for random functions, the decision problem for 3-collision shares the same time-space tradeoff as the 2-collision case \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}}\right) }\) . For general k-collision problems, we extend these results to show that the decision problem over arbitrary functions can be solved in time \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_k}\right) }\) . For the search problem over random functions, we derive two time-space tradeoffs based on the space S, yielding approximately \(S^{1/(k-2)}\) or \(S^{1/(2k-2)}\) -fold speedups compared to the low-memory setting \(S = O(\log M)\) . When \(M = N\) , the tradeoff simplifies to one single curve with \(S^{1/(k-2)}\) -fold speedup.

Revisiting Time-Space Tradeoffs in Collision Search and Decision Problems

会议论文
发表日期：

2026年

查看全文

Jian Guo,
Wenjie Nan,
Yiran Yao

摘要

We present analysis of time-space tradeoffs for both the search and decision variants of the k-collision problem in algorithmic perspective, where \(k \in \left[ 2, O(\operatorname {polylog}(N))\right] \) and the underlying function is \(f_{N,M} : [N] \rightarrow [M]\) with \(M \ge N\) . In contrast to prior work that focuses either on 2-collisions or on random functions with \(M = N\) , our results apply to both random and arbitrary functions and extend to a broader range of k. The tradeoffs are derived from explicit algorithmic constructions developed in this work, especially for decision problems when \(k\ge 3\) . For 2-collision problems, we show that for any random function \(f_{N,M}\) with \(M \ge N\) , the time-space tradeoff for finding all 2-collisions follows a single curve \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}}\right) }\) , where T denotes time complexity and S denotes available space. This tradeoff also extends to arbitrary functions with at most O(N) total 2-collisions. For 3-collision problems, we identify two time-space tradeoff curves for the search variant over random functions, depending on the available space S. For arbitrary functions, we show that the decision problem can be solved with a tradeoff of \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_3}\right) }\) , where \(n_{i}\) denotes the number of i-collisions. Surprisingly, for random functions, the decision problem for 3-collision shares the same time-space tradeoff as the 2-collision case \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}}\right) }\) . For general k-collision problems, we extend these results to show that the decision problem over arbitrary functions can be solved in time \(T=\smash {\widetilde{O}\left( \frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_k}\right) }\) . For the search problem over random functions, we derive two time-space tradeoffs based on the space S, yielding approximately \(S^{1/(k-2)}\) or \(S^{1/(2k-2)}\) -fold speedups compared to the low-memory setting \(S = O(\log M)\) . When \(M = N\) , the tradeoff simplifies to one single curve with \(S^{1/(k-2)}\) -fold speedup.