Analysis of Randomized Algorithms

该研究计划是理论计算机科学。它主要涉及算法的设计和分析，特别是随机化算法，以及动态系统的算法(如网络中的动态负载平衡过程和动态路由问题)。该计划的主要目标是(I)以严格的方式将形式化的方法和技术应用于现实世界的问题，例如，在网络(计算机相关的或其他)中，或在生物学中，以及(Ii)以严格的方式推进形式化(即，数学)用于研究这些模型的方法和技术。将要使用的一个主要工具是随机化算法及其概率分析，或者有时是用于模拟某些现象/场景的结构的概率分析。随机化算法通常是一种非常优雅和高效的方法来解决否则将非常困难(甚至不可能)解决的问题。例如属性测试，这是关于设计和分析算法来验证特定对象(例如，数据库或DNA字符串)是否具有特定属性。随机化算法可以在对象大小呈次线性的时间内做到这一点，即，即使不查看对象的所有部分(尽管必须考虑一定的错误概率)。

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).