A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for general (non-LCL) problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in $O(\log n)$ rounds in the LOCAL model, but requires $\tilde{\Omega}(n^{1/2})$ rounds in the CONGEST model.


翻译:处理本地可核对标签(LCLs)的计算复杂性是一项内容丰富的工作,说明了可能的复杂情况。在本文中,我们研究了在带宽限制下LCL复杂性的景观。我们的主要结果有两个。首先,我们表明,在树木上,LCL问题的CONEST复杂性与LOCOL模型的复杂程度无异。一般(非LLLL)问题的模拟说明已知是虚假的。第二,我们通过提供一个LCL问题,表明LCL可以用LOCAL模型的美元(log n)解决,但在CONEST模型中则需要$(tilde\Omega}(n ⁇ 1/2})美元。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
已删除
将门创投
6+阅读 · 2019年11月21日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月5日
Arxiv
0+阅读 · 2021年7月2日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
6+阅读 · 2019年11月21日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员