We prove a lower bound for distributed algorithms for the Lovász local lemma.
Recently, there have been plenty of upper bounds for algorithmic Lovász local lemma (LLL), also in the context of distributed computing. It is known that there are randomised distributed algorithms that find a correct solution in O(log n) communication rounds, at least in the special case of d = O(1). However, previously only a trivial lower bound of Ω(log* n) was known (LLL can be used to find a colouring of a cycle, and therefore Linial's lower bound for graph colouring applies).
We improve the lower bound from Ω(log* n) to Ω(log log n). This applies to any randomised Monte Carlo distributed algorithm that finds a correct solution w.h.p.
The key idea is to study two closely related graph problems: so-called sinkless orientations and sinkless colourings. It is fairly easy to solve these problems with LLL, so any lower bounds for these problems immediately imply lower bounds for LLL.
We prove the following mutual speedup lemma for high-girth graphs:
— Given an algorithm A for sinkless colouring with a running time of t, we can construct an algorithm B for sinkless orientations with a running time of t.
— Given an algorithm B for sinkless orientations with a running time of t, we can construct an algorithm C for sinkless colouring with a running time of t − 1.
Iterating the lemma, we get a correct algorithm with a running time of 0, which is absurd. For deterministic algorithms in anonymous graphs we get the speedup for free, and hence the lower bound is Ω(log n) by simply plugging in an appropriate graph of girth Θ(log n). For randomised algorithms more care is needed, as error probabilities increase, but we can nevertheless start with an algorithm that is correct w.h.p. and still reach a contradiction after Θ(log log n) iterations of the mutual speedup lemma.
While it is of course nice to have much better lower bounds for LLL, to me the most exciting part here is that this result potentially opens a new line of research related to the distributed time complexity. Overall, the landscape of distributed time complexity is a very complicated beast, but if we focus on bounded-degree graphs, natural graph problems typically fall in one of these classes:
1. Very localised problems that can be solved in time O(1) or O(log* n) in bounded-degree graphs. Typical examples include graph colouring with a sufficiently large number of colours, maximal independent sets, maximal matchings, and approximations of minimum vertex covers and minimum dominating sets.
2. Inherently global problems, with a trivial lower bound of Ω(diameter), even in the case of bounded-degree graphs. Typical examples include spanning tree constructions and maximum matchings.
Now we know that sinkless colourings, sinkless orientations, and LLL fall strictly between these two extremes:
— They cannot be solved in O(log* n) rounds, not even in the case of bounded-degree graphs.
— They can be always solved in polylog(n) rounds, even if the input graph has a linear diameter.
What would be some other graph problems that might have an "intermediate distributed time complexity" in the above sense?
#distributedcomputing #distributedalgorithms #lovaszlocallemma
For the record, here is the statement that I prepared for the council elections: https://users.ics.aalto.fi/suomela/eatcs-2015/
As promised in the statement, I will work towards promoting open access in all EATCS-sponsored events, and to increase the visibility of EATCS, the Bulletin, and theoretical computer science in general in social media.
I would be very happy to hear your thoughts on these matters, and on the activities of EATCS in general.
Call for papers: http://www.podc.org/podc2016/call-for-papers/ — submission deadline 12 February 2016
Call for workshops: http://www.podc.org/podc2016/call-for-workshops/ — deadline for proposals 8 January 2016
— Andrew A. Chien (University of Chicago)
— Faith Ellen (University of Toronto)
— Phillip B. Gibbons (Carnegie Mellon University)
Why the Security of USB Is Fundamentally Broken | Threat Level | WIRED
Computer users pass around USB sticks like silicon business cards. Although we know they often carry malware infections, we depend on antivi
It happened: Git 2.0 is here and it's full of goodies - Atlassian Blogs
Git 2.0 is here and it’s full of goodies. This major release of `git` has been brewing for a long time and I am excited to go on the hunt in
Barcode / QR-Code / Bluetooth / RFID / NFC / DAQ / Label Software: Barco...
News on barcode software, 2D bar code software, Bluetooth, Auto-ID, RFID, AIDC, barcode labeling, reporting software, data acquisition and s
What can be decided locally without identifiers? | Abstract Talk
Abstract. Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context
The On-Line Encyclopedia of Integer Sequences™ (OEIS™)
The On-Line Encyclopedia of Integer Sequences™ (OEIS™). Enter a sequence, word, or sequence number: Hints. Note: Advanced searches are now m
Free online dictionary definitions for learners of English ...
Free online dictionary definitions and pronunciations for learners of English from the bestselling Oxford Advanced Learner's Dictionary.