Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
Xin Lyu, Weihao Zhu · Society for Industrial and Applied Mathematics eBooks · 2023
In the ELEMENT DISTINCTNESS problem, one is given an array a1,…, an of integers from [poly(n)] and is tasked to decide if {ai} are mutually distinct. Beame, Clifford and Machmouchi (FOCS 2013) gave a low-space algorithm for this problem that runs in space S(n) and time T(n) where T(n) ≤ Õ(n3/2/S(n)1/2), assuming a random oracle (i.e., random access to polynomially many random bits). A recent breakthrough by Chen, Jin, Williams and Wu (SODA 2022) showed how to remove the random oracle assumption in the regime S(n) = polylog(n) and T(n) = Õ(n3/2). They designed the first truly polylog(n)-space, Õ(n3/2)-time algorithm by constructing a small family of hash functions H ⊆ {h|h : [poly(n)] → [n]} with a certain pseudorandom property. In this paper, we give a significantly simplified analysis of the pseudorandom hash family by Chen et al. Our analysis clearly identifies the key pseudorandom property required to fool the BCM algorithm, allowing us to explore the full potential of this construction. Based on our new analysis, we show the following. • As our main result, we give a time-space tradeoff for ELEMENT DISTINCTNESS without random oracle. Namely, for every S(n),T(n) such that T ≈ Õ(n3/2/S(n)1/2), our algorithm can solve the problem in space S(n) and time T(n). Our algorithm also works for a related problem SET INTERSECTION, for which this tradeoff is tight due to a matching lower bound by Dinur (Eurocrypt 2020). • As a direct application of our technique, we show a more general pseudorandom property of the hash family, which we call the “c-connecting” property. It might be of independent interest. • The construction by Chen et al. needs O(log3 n log log n) random bits to sample the pseudorandom hash function. We slightly improve the seed length to O (log3 n). * The full version of the paper can be accessed at https://arxiv.org/abs/2210.07534