Maximum Likelihood Estimation and Other Probabilistic Algorithms

CCR-9820885 Kannan，S.该项目在许多领域进行研究，其共同主题是概率算法的设计和分析。最大似然估计是统计学中的经典和重要技术。 通过考虑生成样本数据的特定随机过程来定义这个一般问题的特定版本。 这个问题通常被认为是计算上棘手的最有趣的应用程序。 然而，该项目旨在创建非常有效的算法，以找到近似最可能的解决方案。 具体地，这样的算法被寻求用于计算生物学中的重要问题，例如同源性构建和多重比对。 该项目还研究了推理置信网问题的类似方法，置信网是人工智能中流行的随机模型。竞争问题与以太网上的消息传输有关，其中消息根据随机过程（如泊松过程）到达。 每个消息都使用一个协议，它试图在每个时刻以一定的概率传输自己。一个中心的开放问题是是否有一个协议，以确保系统是“稳定的”。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.