English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In the Element Distinctness problem, one is given an array $a_1,\dots, a_n$of integers from $[poly(n)]$ and is tasked to decide if $\{a_i\}$ are mutuallydistinct. Beame, Clifford and Machmouchi (FOCS 2013) gave a low-space algorithmfor this problem running in space $S(n)$ and time $T(n)$ where $T(n) \le\widetilde{O}(n^{3/2}/S(n)^{1/2})$, assuming a random oracle (i.e., randomaccess to polynomially many random bits). A recent breakthrough by Chen, Jin,Williams and Wu (SODA 2022) showed how to remove the random oracle assumptionin the regime $S(n) = polylog(n)$ and $T(n) = \widetilde{O}(n^{3/2})$. Theydesigned the first truly $polylog(n)$-space, $\widetilde{O}(n^{3/2})$-timealgorithm by constructing a small family of hash functions $\mathcal{H}\subseteq \{h | h:[poly(n)]\to [n]\}$ with a certain pseudorandom property.  In this paper, we give a significantly simplified analysis of thepseudorandom hash family by Chen et al. Our analysis clearly identifies the keypseudorandom property required to fool the BCM algorithm, allowing us toexplore the full potential of this construction. As our main result, we show atime-space tradeoff for Element Distinctness without random oracle. Namely, forevery $S(n),T(n)$ such that $T\approx \widetilde{O}(n^{3/2}/S(n)^{1/2})$, ouralgorithm can solve the problem in space $S(n)$ and time $T(n)$. Our algorithmalso works for a related problem Set Intersection, for which this tradeoff istight due to a matching lower bound by Dinur (Eurocrypt 2020). As twoadditional contributions, we show a more general pseudorandom property of thehash family, and slightly improve the seed length to sample the pseudorandomhash function.

Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness