Date: Sunday, 25 Adar I 5765 (March 6, '05)

Speaker: Dr. Boaz Tsaban (Weizmann Institute of Science)

Title: "Permutation graphs and fast forward permutations"

Abstract:
---------
A permutation P on {1,..,N} is a _fast_forward_permutation_ if for each m
the computational complexity of evaluating P^m(x) is small independently
of m and x. Naor and Reingold constructed fast forward pseudorandom
cycluses, and asked whether fast forward (general) pseudorandom
permutations can be constructed. We provide a positive answer by
introducing an efficient method to sample the cycle structure of a random
permutation. This constitutes the first part of the talk.

In the second part of the talk we address the question of
distinguishability of random cycluses from arbitrary permutations with
queries of the form P(x) or P^{-1}(x) only. By studying the evolution of
permutation graphs, we prove that the number of queries needed to
distinguish a random cyclus from a random permutation on {1,..,N}, using
such queries, is Theta(N). This settles a conjecture of Naor and Reingold.

If time permits, we will also briefly discuss very recent results on a
related construction by Oded Goldreich, Shafi Goldwasser and Asaf
Nussboim.