Maximum Likelihood Estimation and Other Probabilistic Algorithms

这个项目在许多领域进行研究，共同的主题是概率算法的设计和分析。极大似然估计是统计学中一项经典而重要的技术。通过考虑生成样本数据的特定随机过程来定义这个一般问题的特定版本。对于大多数有趣的应用程序，这个问题通常被认为是难以计算的。然而，这个项目寻求创建非常有效的算法，以找到大约最可能的解决方案。特别是这样的算法被用于计算生物学中的重要问题，如系统发育构建和多重比对。该项目还研究了推理信念网问题的类似方法，这是人工智能中流行的随机模型。争用问题涉及以太网上的消息传输，其中消息根据随机过程（如泊松过程）到达。每条消息都使用一种协议，通过这种协议，它试图在每个时刻以一定的概率传输自己。一个悬而未决的核心问题是，是否有一个协议可以确保系统“稳定”。PI证明，对于许多“自然”类型的协议来说，答案是“不”，并且正在努力将这些证明扩展到所有基于确认的协议。最后，研究了程序检查领域的新模型和问题，其中也涉及随机算法的设计。

CCR-9820885Kannan, S.This project pursues research in a number of areas with the common theme being the design and analysis of probabilistic algorithms.Maximum Likelihood Estimation is a classical and important technique in statistics. Specific versions of this general problem are defined by considering specific stochastic processes that generate the sample data. This problem has generally been thought to be computationally intractable for most interesting applications. However, this project seeks to create very efficient algorithms that find approximately the most likely solutions. Specifically such algorithms are sought for important problems in computational biology such as phylogeny construction and multiple alignment. The project also investigates similar approaches for the problem of inferring Belief Nets, a popular stochastic model in artificial intelligence.The problem of contention is concerned with message transmission over an ethernet where messages arrive according to a stochastic process such as a Poisson process. Each message uses a protocol whereby it attempts to transmit itself at each time instant with some probability.A central open question is whether there is a protocol that ensures that the system is "stable." The PI proved that the answer is "no" for a number of "natural" classes of protocols and is working on extending these proofs to all acknowledgement-based protocols. Finally, the project investigate new models and problems in the area of program checking which again involves the design of randomized algorithms.