检索结果-内蒙古大学图书馆

43rd ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing, PODC 2024

作者： Balliu, Alkida Brandt, Sebastian Kuhn, Fabian Olivetti, Dennis Schmid, Gustav Gran Sasso Science Institute L'Aquila Italy Cispa Helmholtz Center for Information Security Saarbrücken Germany University of Freiburg Freiburg Germany

ISBN: (纸本)9798400706684

The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of research with regards to this new complexity measure is to understand the complexity landscape of locally checkable labelings (LCLs) on families of bounded-degree graphs. Particularly interesting in this context is the family of bounded-degree trees as there, for the worst-case complexity, we know a complete characterization of the possible complexities and structures of LCL problems. A first step for the node-averaged complexity case has been achieved recently [DISC '23], where the authors in particular showed that in bounded-degree trees, there is a large complexity gap: There are no LCL problems with a deterministic node-averaged complexity between ω(log∗n) and no(1). For randomized algorithms, they even showed that the node-averaged complexity is either O(1) or nω(1). In this work we fill in the remaining gaps and give a complete description of the node-averaged complexity landscape of LCLs on bounded-degree trees. Our contributions are threefold.•On bounded-degree trees, there is no LCL with a node-averaged complexity between ω(1) and (log∗n)o(1).•For any constants 0 1 2 ≤ 1 and ϵ > 0, there exists a constant c and an LCL problem with node-averaged complexity between ω((log∗n)c) and O((log∗n)c+ϵ).•For any constants 0 0, there exists an LCL problem with node-averaged complexity Φ(nx) for some x ϵ [α, α + ϵ]. © 2024 Association for Computing Machinery. All rights reserved.

关键词： locally checkable labelings node-averaged complexity distributed complexity theory

来源：评论

学校读者我要写书评

暂无评论

The Landscape of distributed Complexities on Trees and Beyond 22

The Landscape of Distributed Complexities on Trees and Beyon...

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Grunau, Christoph Rozhon, Vaclav Brandt, Sebastian Swiss Fed Inst Technol Zurich Switzerland CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

ISBN: (纸本)9781450392624

We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below log* n. Our contribution is threefold: (1) Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity o (log* n) has actually complexityO(1). This result improves upon the previous speedup result from o (log log* n) to O(1) by [Chang, Pettie, FOCS 2017]. (2) In the related LCA and VOLUME models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020],we prove the same speedup from o (log* n) to O(1) for all constant-degree graphs. (3) Similarly, we complete the classification of the LOCAL complexity landscape of oriented d-dimensional grids by proving that any LCL problem with local complexity o (log* n) has actually complexity O(1). This improves upon the previous speed-up from o ((d)root log* n) by Suomela, explained in [Chang, Pettie, FOCS 2017].

关键词： graph problems LCL problems distributed complexity theory locality LOCAL model volume model gap result

来源：评论

学校读者我要写书评

暂无评论

Almost global problems in the LOCAL model

引用

distributed COMPUTING 2021年第4期34卷 259-281页

作者： Balliu, Alkida Brandt, Sebastian Olivetti, Dennis Suomela, Jukka Aalto Univ Espoo Finland Swiss Fed Inst Technol Zurich Switzerland

The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges: - There are lots of problems with time complexities of Theta(log* n) or Theta(log n). - It is not possible to have a problem with complexity between omega(log* n) and o(log n). - Ingeneral graphs, we can construct LCL problems with infinitely many complexities between.(log n) and no(1). - Intrees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are LCL problems with complexities of the form Theta(n(alpha)) for any rational 0 < a = 1/2, while for trees only complexities of the form Theta(n(1/k)) are known. No LCL problem with complexity between omega(root n) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that: - Ingeneral graphs, we can construct LCL problems with infinitely many complexities between omega(root n) and o(n). - Intrees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity on) can be solved in time O(root n) in trees, while the same is not true in general graphs.

关键词： distributed complexity theory Locally checkable labellings LOCAL model

来源：评论

学校读者我要写书评

暂无评论

Hardness of Minimal Symmetry Breaking in distributed Computing 19

Hardness of Minimal Symmetry Breaking in Distributed Computi...

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Balliu, Alkida Hirvonen, Juho Olivetti, Dennis Suomela, Jukka Aalto Univ Helsinki Finland

ISBN: (纸本)9781450362177

A graph is weakly 2-colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we study the distributed computational complexity of weak 2-coloring in the standard LOCAL model of distributed computing, and how it is related to the distributed computational complexity of other graph problems. First, we show that weak 2-coloring is a minimal distributed symmetry-breaking problem for regular even-degree trees and highgirth graphs: if there is any non-trivial locally checkable labeling problem that is solvable in o(log* n) rounds with a distributed graph algorithm in the middle of a regular even-degree tree, then weak 2-coloring is also solvable in o(log* n) rounds there. Second, we prove a tight lower bound of Omega(log* n) for the distributed computational complexity of weak 2-coloring in regular trees;previously only a lower bound of Omega(log log* n) was known. By minimality, the same lower bound holds for any non-trivial locally checkable problem inside regular even-degree trees.

关键词： distributed complexity theory graph algorithms locally checkable labelings LOCAL model

来源：评论

学校读者我要写书评

暂无评论

New Classes of distributed Time complexity 2018

New Classes of Distributed Time Complexity

引用

50th Annual ACM SIGACT Symposium on the theory of Computing (STOC)

作者： Balliu, Alkida Hirvonen, Juho Korhonen, Janne H. Lempiainen, Tuomo Olivetti, Dennis Suomela, Jukka Aalto Univ Espoo Finland Gran Sasso Sci Inst Laquila Italy Inst Rech Informat Fondamentale Paris France Univ Freiburg Freiburg Germany CNRS IRIF Paris France Univ Paris Diderot Paris France

ISBN: (纸本)9781450355599

A number of recent papers - e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) - have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem II in which a solution can be verified by checking all radius-O(1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius-T neighbourhood. Here T is the distributed time complexity of Pi. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Theta(1), Theta(log* n), Theta(log n), Theta(n(1/k)), and Theta(n). It is also known that there are two gaps: one between omega(1) and o(log log* n), and another between omega(log* n) and o(log n). It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple - indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Theta(log(alpha) n) for any alpha > 1, 2(Theta(log alpha n)) for any alpha <= 1, and Theta(n(alpha)) for any alpha < 1/2 in the high end of the complexity spectrum, and Theta(log(alpha) log* n) for any alpha >= 1, 2(Theta(log alpha log* n)) for any alpha <= 1, and (Theta)((log* n)(alpha)) for any alpha <= 1 in the low end of the complexity spectrum;here alpha is a positive rational number.

关键词： distributed complexity theory graph algorithms locally checkable labellings LOCAL model

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：