Analysis of Randomized Algorithms

点击翻译按钮获取中文摘要

The proposed research program is in Theoretical Computer Science.  It is mainly concerned with the design and analysis of algorithms, and here, in particular,  randomized algorithms, and algorithms for dynamic systems (like dynamic load balancing processes and dynamic routing problems in networks).The main goals of this program are (i) to apply formal methods and techniques to real-world problems, e.g., in Networking (computer-related or otherwise), or in Biology, in a rigorous way, and(ii) to advance the formal (i.e., mathematical) methods and techniques used to study these models.  One main vehicle that is going to be used is that of randomized algorithms and their probabilistic analysis, or sometimes ``just'' the probabilistic analysis of structures used to model certain phenomena/scenarios.Randomized algorithms are typically a very elegant and efficient way of solving problems that would otherwise be very hard (or even impossible) to solve.  An example would be Property Testing, which is about devising and analyzing algorithms that verify whether or not a certain object (e.g., a database, or a DNA string) has a certain property. Randomized algorithms can do that in time that is sub-linear in the size of the object, i.e., even without looking at all parts of the object (one must allow for a certain error probability though).