Title：What can be sampled locally?

时间:11月21日上午10:00

地点：东五楼210

Abstract：

The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] studies whether a locally defined distributed computing problem is locally solvable. In classic local computation tasks, the goal of distributed algorithms is to construct a feasible solution for some constraint satisfaction problem (CSP) locally defined on the network.

In this talk, we consider the problem of sampling a uniform CSP solution by distributed algorithms in the LOCAL model, and ask whether a locally definable joint distribution is locally sample-able. We use Markov random fields (MRFs) and Gibbs distributions to model locally definable joint distributions. We give two Markov chain based distributed sampling algorithms, called “LubyGlauber" and “LocalMetropolis", which we believe to represent two basic approaches for distributed Gibbs sampling. The algorithms achieve respective mixing times $O(\Delta\log n)$ and $O(\log n)$ under typical mixing conditions. We show that the time bound $\Theta(\log n)$ is optimal for distributed sampling. We also show a strong $\Omega(diam)$ lower bound: in particular for sampling independent set in graphs with maximum degree $\Delta\ge 6$. This gives a strong separation between sampling and constructing locally checkable labelings.

Bio:

尹一通，南京大学计算机科学与技术系教授，博士生导师；2009年博士毕业于耶鲁大学，同年回到本科母校南京大学任教。开设课程：随机算法、组合数学、高级算法。研究方向：理论计算机科学。主要研究兴趣：（1）现代算法理论——例如随机算法、采样与计数算法、分布式算法等；（2）复杂性下界——例如数据结构复杂性、通讯复杂性、分布式计算下界等。 目前已在FOCS、SODA、ICALP、PODC、SPAA等理论计算机科学国际会议发表二十余篇论文，获得并行算法国际会议SPAA 2016优秀论文（outstanding paper）奖，并于2016年受邀参加UC Berkeley举办的“计数复杂性与相变”访问项目。2009年入选教育部新世纪优秀人才支持计划；2011年入选微软研究院“铸星计划”；2014年获中创软件人才奖；2017年获得国家自然科学基金优秀青年科学基金“理论计算机科学”。