CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37

最新内容

The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lov\'asz Local Lemma (LLL) on constant degree graphs is $\Theta(\log n)$. The lower bound follows by proving an $\Omega(\log n)$ lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of $o(\sqrt{\log{n}})$ can be turned into a deterministic LCA algorithm with a probe complexity of $O(\log^* n)$. This improves exponentially upon the currently best known speed-up result from $o(\log \log n)$ to $O(\log^* n)$ implied by the result of [Chang, Pettie FOCS 2017] in the LOCAL model. Finally, we show that for every fixed constant $c \geq 2$, the deterministic VOLUME complexity of $c$-coloring a bounded degree tree is $\Theta(n)$, where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020].

0
0
下载
预览

最新论文

The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lov\'asz Local Lemma (LLL) on constant degree graphs is $\Theta(\log n)$. The lower bound follows by proving an $\Omega(\log n)$ lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of $o(\sqrt{\log{n}})$ can be turned into a deterministic LCA algorithm with a probe complexity of $O(\log^* n)$. This improves exponentially upon the currently best known speed-up result from $o(\log \log n)$ to $O(\log^* n)$ implied by the result of [Chang, Pettie FOCS 2017] in the LOCAL model. Finally, we show that for every fixed constant $c \geq 2$, the deterministic VOLUME complexity of $c$-coloring a bounded degree tree is $\Theta(n)$, where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020].

0
0
下载
预览
参考链接
Top