Influence of Boolean Functions and Gibbs Measures on Trees: Foundations and Applications

研究者使用高斯希尔伯特空间研究布尔函数的影响。研究者对社会选择理论、近似硬度和学习理论中出现的问题特别感兴趣。研究人员使用概率和统计物理学的技术，特别是树上的吉布斯测度理论，进一步研究了许多图模型的推理算法。这些算法用于系统发育推断、计算马尔可夫随机场中的边际以及解决可满足性问题。在第一个主题中，研究者研究以下问题：“我们如何设计可靠的投票方案？”投票机的错误对投票结果有何影响？同样的数学问题对于理解高性能计算中出现的理论问题也很重要，特别是用于近似解决“困难”问题的有效算法的存在。在第二个主题中，研究者受到现代生物学和医学研究核心的祖先关系问题以及在专家系统和数据挖掘中发挥重要作用的高维统计推断问题的激励。

The investigator studies influences ofboolean functions using Gaussian Hilbert spaces.The investigator is interested in particular in problemsarising in the theory of social choice, in hardness of approximation andin learning theory. The investigator further studies a number of inference algorithms on graphical models using techniques from probability andstatistical physics in general and the theory of Gibbs measureson trees in particular. These algorithms are used for phylogeneticinference, for computing marginals in Markov random fields and for solvingsatisfiability problems.In the first topic the investigator studies questions like: ``How dowe design a reliable voting scheme? What is the effect of error invoting machines on the outcome of a vote?''. The same mathematicalquestions are also important in understandingtheoretical questions arising in high-performance computing, inparticular the existence of efficient algorithms for approximatelysolving ``hard'' problems. In the second topic, the investigator ismotivated by questions on ancestral relationship that are central inmodern biological and medical research, and in problems ofhigh-dimensional statistical inference that play an important role inexpert systems and data-mining.