The objective of this research is to establish methods for theoretical study in an important area of theoretical computer science, which is the analysis of randomized algorithms. The main focus is on problems that either can be modeled by Markov chains or can be analyzed using the Markov chain approach.
This project concentrates on three main topics: (1) general analysis of discrete-time Markov chains and the Monte Carlo Markov Chain method, (2) analysis of Markov chains for generating random permutations, and (3) resource allocation problems in distributed systems.
In the area of general analysis of Markov chains the goal of the research is to develop new tools for the analysis of mixing times of Markov chains. An important part of this study is to investigate relationships between various known methods of the analysis of mixing times of Markov chains.
In the investigations of Markov chains for generating random permutations the main focus is on so called random switching networks. These networks model behavior of many Markov chains that are sought in applications in cryptography.
In the area of resource allocation problems in distributed systems, the research focuses mostly on resource allocation problems in networks, in which the cost of the allocation depend on the routing properties of the input network as well as on the contention resolution protocols applied to the system.
