We present an intimate connection among the following fields: (a) distributed local algorithms: coming from the area of computer science, (b) finitary factors of iid processes: coming from the area of analysis of randomized processes, (c) descriptive combinatorics: coming from the area of combinatorics and measure theory. In particular, we study locally checkable labellings in grid graphs from all three perspectives. Most of our results are for the perspective (b) where we prove time hierarchy theorems akin to those known in the field (a) [Chang, Pettie FOCS 2017]. This approach that borrows techniques from the fields (a) and (c) implies a number of results about possible complexities of finitary factor solutions. Among others, it answers three open questions of [Holroyd et al. Annals of Prob. 2017] or the more general question of [Brandt et al. PODC 2017] who asked for a formal connection between the fields (a) and (b). In general, we hope that our treatment will help to view all three perspectives as a part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn 2020+] .


翻译:我们展示了以下领域的紧密联系:(a) 分布式本地算法:(a) 分布式本地算法:来自计算机科学领域的本地算法;(b) iid过程的原始因素:来自随机化过程分析领域;(c) 描述性组合法:(c) 描述性组合法:来自组合法和测量理论领域;特别是,我们从所有三个角度研究网格图中的可本地核对标签;我们的大多数结果都来自以下角度:(b) 我们证明时间等级的标语类似于实地已知的标语(a) [Chang, Pettie FOCS 2017];这种方法从领域借用技术(a) 和(c) 意味着关于氟化因素解决方案可能的复杂性的若干结果;除其他外,它回答了[Holroud et al. Annals of Prob. 201717] 三个公开的问题,或更笼统的[Brandt et al. POCDC 2017] 问题,他们要求将领域(a)和(b) 正式连接起来。我们希望我们的处理方法将有助于将所有三个观点视为2020年共同理论的一部分。

0
下载
关闭预览

相关内容

PODC:ACM Symposium on Principles of Distributed Computing。 Explanation:分布式计算原理学术讨论会。 Publisher:ACM。 SIT: http://dblp.uni-trier.de/db/conf/podc/
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
17+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
18+阅读 · 2020年10月9日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
AutoML: A Survey of the State-of-the-Art
Arxiv
67+阅读 · 2019年8月14日
Arxiv
8+阅读 · 2018年11月27日
VIP会员
相关VIP内容
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
17+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Top
微信扫码咨询专知VIP会员