CAREER: Applications of Probability Theory in Computer Science, Social Choice, Biology and Statistics

职业：概率论在计算机科学、社会选择、生物学和统计学中的应用

• 批准号: 0548249
• 负责人: Elchanan Mossel
• 金额: $ 40万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0548249&HistoricalAwards=false
• 关键词: CAREER; Applications; Probability; Theory; Computer

The investigator studies the robustness of functions to stochastic perturbation of their inputs in terms of the influences of each variable on the function. The investigator is interested in particular in problems arising in the theory of social choice in economy and in hardness of approximation in theoretical computer science and their relation to classical and Gaussian isoperimetric problems. The investigator further studies properties of Gibbs measures on trees in relation to algorithmic inference problems on Markov random fields. In particular, provably efficient algorithms for phylogenetic inference are developed. In the first topic the investigator studies questions like: ``How do we design a reliable voting scheme? What is the effect of error in voting machines on the outcome of a vote?''. The same mathematical questions are also an important ingredient in understanding theoretical questions arising in high-performance computing, in particular the existence of efficient algorithms that approximately solve ``hard'' problems. In the second topic, the investigator is motivated by questions on ancestral relationship that are central in modern biological, medical and genealogical research, and in problems arising in high-dimensional statistical inference which play an important role in expert systems and data-mining.

研究者根据每个变量对函数的影响来研究函数对其输入随机扰动的鲁棒性。研究者特别感兴趣的是经济中的社会选择理论和理论计算机科学中的近似硬度问题，以及它们与经典和高斯等周问题的关系。研究者进一步研究了树上Gibbs测度与马尔可夫随机场上的算法推理问题的性质。特别是，开发了可证明有效的系统发育推断算法。在第一个主题中，研究者研究了这样的问题：“我们如何设计一个可靠的投票方案？”投票机的错误对投票结果有什么影响？”同样的数学问题也是理解高性能计算中出现的理论问题的重要组成部分，特别是存在近似解决“难”问题的有效算法。在第二个主题中，研究者的动机是关于祖先关系的问题，这是现代生物学，医学和家谱研究的核心问题，以及在专家系统和数据挖掘中发挥重要作用的高维统计推断中出现的问题。