Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems

合作研究：AF：小：采样相关问题中的相变

基本信息

批准号：
2205743
负责人：
Eric Vigoda
金额：
$ 24.99万
依托单位：
University of California-Santa Barbara
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2205743&HistoricalAwards=false
关键词：
Collaborative Research AF Small Phase

项目摘要

Graphical models are a widely used tool to succinctly represent high-dimensional data and to understand the fundamental building blocks and interactions of physical and biological systems. These models have appeared in a variety of scientific fields. In physics they are used to understand the thermodynamic properties of ferromagnetic materials and are integral in the study of phase transitions in physical systems. In biology these models are a fundamental tool for inferring evolutionary history using genetic data in phylogenetic models. Graphical models are ubiquitous in machine learning for computational tasks such as Bayesian inference. This project addresses fundamental computational tasks that are crucial for studying, constructing, and utilizing graphical models. The project will involve undergraduate students in research involving graphical models in social science settings.There are two core tasks for studying graphical models: learning and sampling. The learning problem is focused on inferring the inner structure of the underlying graphical model from the macroscopic behavior of the system. In contrast, the goal of the associated sampling problem is to efficiently simulate the thermodynamic behavior of a learned or inferred graphical model. This project will develop new algorithms, and more generally understand the computational complexity of sampling and learning as well as several related problems. A common theme in this project is connecting the computational complexity of these sampling- and inference-related problems with statistical-physics phase transitions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图形模型是一种广泛使用的工具，可简洁地表示高维数据并理解物理和生物系统的基本构建块和相互作用。这些模型已经出现在各个科学领域。在物理学中，它们用于了解铁磁材料的热力学性质，并且是物理系统相变研究中不可或缺的一部分。在生物学中，这些模型是使用系统发育模型中的遗传数据推断进化历史的基本工具。图形模型在贝叶斯推理等计算任务的机器学习中无处不在。该项目解决了对于研究、构建和利用图形模型至关重要的基本计算任务。该项目将让本科生参与社会科学环境中图模型的研究。研究图模型有两个核心任务：学习和采样。学习问题的重点是从系统的宏观行为推断底层图模型的内部结构。相反，相关采样问题的目标是有效地模拟学习或推断的图形模型的热力学行为。该项目将开发新的算法，并更普遍地了解采样和学习的计算复杂性以及几个相关问题。该项目的一个共同主题是将这些采样和推理相关问题的计算复杂性与统计物理相变联系起来。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优势和更广泛的影响进行评估，被认为值得支持审查标准。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Counting and Sampling Labeled Chordal Graphs in Polynomial Time

在多项式时间内对标记的弦图进行计数和采样

DOI：
发表时间：
2023-09
期刊：
31st Annual European Symposium on Algorithms (ESA
影响因子：
0
作者：
Hébert;Lokshtanov, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

坐标条件采样高维身份测试的复杂性

DOI：
发表时间：
2023-07
期刊：
Proceedings of 36th Conference on Learning Theory (COLT
影响因子：
0
作者：
Blanca, Antonio;Chen, Zongchen;Štefankovič, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Approximating Observables Is as Hard as Counting

近似可观测值与计数一样困难

DOI：
发表时间：
2022-07
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Galanis, Andreas;Štefankovič, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Improved Distributed Algorithms for Random Colorings

改进的随机着色分布式算法

DOI：
10.4230/lipics.opodis.2023.13
发表时间：
2023-12
期刊：
27th International Conference on Principles of Distributed Systems (OPODIS 2023
影响因子：
0
作者：
Carlson, Charlie;Frishberg, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Metastability of the Potts Ferromagnet on Random Regular Graphs

随机正则图上波兹铁磁体的亚稳态

DOI：
发表时间：
2022-07
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Coja;Galanis, Andreas;Goldberg, Leslie Ann;Ravelomanana, Jean Bernoulli;Štefankovič, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric