A rich line of work has been addressing the computational complexity of locally checkable labelings (\LCL{}s), 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.


翻译:处理本地可核对标签的计算复杂性(\ LCL ⁇ s) 是一项内容丰富的工作, 说明了可能的复杂情况。 在本文中, 我们研究了带宽限制下的 LCL 复杂性。 我们的主要结果有双重。 首先, 我们显示在树上,\ LCOL 问题的复杂性与 \ LCOL 模型中的复杂程度无异。 一般( 非 LCL ⁇ s) 问题的类比说明是假的。 第二, 我们通过提供 \ LCL 问题来显示, 对于一般图表来说, 这一等值并不有效, 我们显示, 在 \ LCOL 模型中, 它可以用 $( log n) 来解决, 但是在\ CONEST 模型中, 需要$\ tilde\ Omega} (n\ 1/2} 。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
专知会员服务
42+阅读 · 2020年12月18日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
155+阅读 · 2020年5月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月1日
Backgammon is Hard
Arxiv
0+阅读 · 2021年6月30日
VIP会员
相关VIP内容
【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
专知会员服务
42+阅读 · 2020年12月18日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
155+阅读 · 2020年5月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员