局部采样的算法与复杂性

Locality is a classic theme for computation. The study of local computation asks the following fundamental question: "Are locally definable problems locally computable?" The studies of local computation are focused on decision, optimization, or search problems defined by constraint satisfaction problems (CSP). These computational problems concerns about properties of individual CSP solutions. There is another fundamental aspect of constraint satisfaction problems: namely, the computational problems that concerns about the properties of the population of all CSP solutions. Such problems are represented by sampling problems: in particular, sampling a random CSP solution, or more generally, sampling from a joint distribution described by locally dependent random variables. In the proposed research project, we ask an innovative yet fundamental question: "How to sample using local information from a locally dependent joint distribution?" This research problem synthesizes years of theoretical studies from three areas: sampling algorithms, communication complexity, and the theory of distributed computing. The study of this proposed problem will initiate an investigation of an unexplored yet very important area of Theoretical Computer Science. Meanwhile, it also has significant implications in practical aspects of Computer Science.

计算的局部性是计算机科学的一个经典主题。局部计算（local computation）关注如下基础性论题：“可局部定义的问题，是否可被局部计算”。局部计算解决的是约束满足问题（CSP），而传统的局部计算解决的是约束满足问题的判定、优化、搜索等关注单个CSP满足解性质的计算问题。而约束满足问题的另一个重要方面是关于全体解性质的计算问题，其中最具代表性的就是采样问题——即对约束满足问题的解进行随机采样，或者者更具一般性的：从彼此相关的随机变量定义的联合分布中进行随机采样。本项目创新性的提出了“从局部相关的联合分布中，如何利用局部信息进行随机采样？”这一基础性理论问题。该问题汇集了来自采样算法、通信复杂性、分布式计算理论三个方面的理论研究。对该问题的探索，将填补理论计算机科学的一项空白，同时也具有极其重要的应用价值。

计算的局部性是计算机科学的一个经典主题。局部计算 (local computation) 关注如下基础性论题：“可局部定义的问题，是否可被局部计算”。局部计算解决的是约束满足问题 (CSP)，而传统的局部计算解决的是约束满足问题的判定、优化、搜索等关注单个CSP满足解性质的计算问题。而约束满足问题的另一个重要方面是关于全体解性质的计算问题，其中最具代表性的就是采样问题——即对约束满足问题的解进行随机采样，或者更具一般性的：从彼此相关的随机变量定义的联合分布中进行随机采样。本项目创新性 的提出了“从局部相关的联合分布中，如何利用局部信息进行随机采样?”这一基础性理论问题。该问题汇集了来自采样算法、通信复杂性、分布式计算理论三个方面的理论研究 。本项目对该问题进行了系统的探索，填补理论计算机科学的一项空白，取得若干重要进展。成果发表在理论计算机科学国际会议STOC（3篇）、SODA（2篇）、PODC（3篇）、SPAA、ICALP，以及国际期刊SICOMP、IANDC等。