Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.

This problem has a stunning solution running in $O(n)$ time and using 2 words of space only, attributed to Bob Floyd (at least by Knuth). The crux is to see this as a cycle finding problem (even though there is zero mention of a cycle let alone a graph), and employ the so called Tortoise and Hare algorithm (again, by Floyd).

This Tortoise and Hare algorithm was later used by Pollard in his factoring algorithm and somewhat recently extended here to solve the element distinctness problem using small space.

What are some other uses of this algorithm or extensions of it in TCS?

  • 1
    $\begingroup$ Pollard used for dlog. Do you have references for factoring? $\endgroup$ – 1.. Jul 11 '19 at 23:11
  • 1
    $\begingroup$ @Turbo en.wikipedia.org/wiki/Pollard%27s_rho_algorithm $\endgroup$ – boinkboink Jul 12 '19 at 0:01
  • $\begingroup$ Maybe not in TCS, but it can be used to find collisions in Hash Functions with $O(2^{n/2})$ time and just a bit of memory. $\endgroup$ – Fractalic Jul 17 '19 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.