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

布尔函数和吉布斯测度对树的影响：基础和应用

• 批准号: 0504245
• 负责人: Elchanan Mossel
• 金额: --
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0504245&HistoricalAwards=false
• 关键词: Influence; Boolean; Functions; Gibbs; Measures

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.

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