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

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

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.