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