ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Models of Random Mappings

Speaker: Jerzy Jaworski
Date, Time: Fri, 23 Apr 2010 15:00

We give a short overview of random mappings models. These models have natural applications in cryptology. In particular, questions concerning the structure of random digraphs representing mappings arise in the analysis of cryptographic systems (e.g. DES), in applications of Pollard's algorithm, in simulations of shift register sequences, and in computational number theory and random number generation. To date, the most widely studied models have been special cases of a model whose key feature is that each vertex in the corresponding digraph `chooses' the vertex that it is mapped to independently of the `choices' made by all other vertices. Here we consider random mappings for which the vertex `choices' are not necessarily independent. In particular, a general model is constructed by first specifying the in-degrees of the vertices (using a collection of non-negative integer-valued exchangeable random variables) and then selecting a random mapping uniformly from all mappings with the given in-degree sequence. We focus on the properties of two special cases - the preferential and anti-preferential attachment models.

Back to the top of this page