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

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

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.