Strong Law of Large Numbers for Graph(Group)-Valued Random Elements

12 PM on Thursday, April 2nd, 2009; NAC 4/115

Dr. Alexander Ushakov (Stevens Institute of Technology)

We introduce the notion of the mean-set (expectation) of a graph-(group-) valued random

element $\xi$ and prove a generalization of the strong law of large numbers on graphs and groups.

Furthermore, we prove an analogue of the classical Chebyshev's inequality for $\xi$.В We show that our

generalized law of large numbers, as a new theoretical tool, provides a framework for practical

applications; namely, it has implications for cryptanalysis of group-based authentication

protocols.В In addition, we prove several results about configurations of mean-sets in graphs and

their applications. In particular, we discuss computational problems and methods of computing of

mean-sets in practice and propose an algorithm for such computation.

Programs