## Profile

## Stream

### Jukka Suomela

Shared publicly -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

### Jukka Suomela

Shared publicly -**EATCS council**: http://www.eatcs.org/index.php/council — many thanks to all of you who voted for me!

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.

#eatcs #tcs

2

1

### Jukka Suomela

Shared publicly -### Jukka Suomela

Shared publicly -Yes, it works so that you can have e.g. Sublime Text and Skim side-by-side, with your Latex document open in Sublime Text, and PDF preview visible in Skim.

### Jukka Suomela

Shared publicly -### Jukka Suomela

Shared publicly -### Jukka Suomela

Shared publicly -### Jukka Suomela

Shared publicly -### Jukka Suomela

Shared publicly -**PODC 2016**, 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, will be held in

**Chicago**on

**25–28 July 2016**: http://www.podc.org/

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**

Keynote Speakers:

— Andrew A. Chien (University of Chicago)

— Faith Ellen (University of Toronto)

— Phillip B. Gibbons (Carnegie Mellon University)

#distributedcomputing #PODC2016Chicago

- aalto.fi (current)

Why the Security of USB Is Fundamentally Broken | Threat Level | WIRED www.wired.com 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 blogs.atlassian.com 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 |

Best paper awards at ICALP 2014 processalgebra.blogspot.com The EATCS is proud to announce that the program committees of the three tracks of ICALP 2014 have selected the following papers for the best |

Barcode / QR-Code / Bluetooth / RFID / NFC / DAQ / Label Software: Barco... tec-it.blogspot.com News on barcode software, 2D bar code software, Bluetooth, Auto-ID, RFID, AIDC, barcode labeling, reporting software, data acquisition and s |

Moves market.android.com Moves automatically tracks your everyday life and exercise. Just carry your phone in your pocket or bag. FEATURES • Automatic Tracking: Reco |

Google Play Книги market.android.com Google Play – это настоящий рай для книголюбов. В этом интернет-магазине вас ждут миллионы книг, в том числе бесплатных. Выберите из новинок |

GPS Test market.android.com The GPS Test app for Android is a utility that shows GPS information read from your phones internal GPS. Will support GLONASS phones. The ap |

Google Play Music market.android.com Google Play Music makes it easy to discover, play and share the music you love on Android and the web. With our new All Access service, you |

Feedly News Reader. Blogs. RSS market.android.com "Feedly is what you needly" - David Pogue, New York Times.Feedly is a new way to browse the content of your favorite news sites, rss feeds, |

Dropbox market.android.com Dropbox 提供免費的服務，讓您可以隨時隨地存取您所有的相片、文件和影片。一旦在電腦上安裝了 Dropbox，您儲存在 Dropbox 的任何檔案都會自動儲存到您所有的電腦、手機及 Dropbox 網站。有了 Dropbox 應用程式，您可以把重要的東西全部帶著走。即使是出門 |

Andropas Pro market.android.com Andropas Pro lisää uusia ominaisuuksia Andropas-ohjelmaan. Tue Andropaksen kehitystä ja osta Andropas Pro.Ominaisuudet: - Suosikkipysäkit ja |

younited by F-Secure market.android.com With younited you can have all your stuff in a safe cloud. You can access your pictures, videos, music and docs with your Android and other |

The selected-papers network gowers.wordpress.com This post is to report briefly on a new and to my mind very exciting venture in academic publishing. It's called the Selected Papers Network |

What can be decided locally without identifiers? | Abstract Talk www.abstract-talk.org 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™) oeis.org The On-Line Encyclopedia of Integer Sequences™ (OEIS™). Enter a sequence, word, or sequence number: Hints. Note: Advanced searches are now m |

ACM Digital Library portal.acm.org www.acm.org - The premier society in computing brings you the Computer Portal. |

Fingerpori - HS.fi www.hs.fi Löydät Fingerporin Heimon, Allanin ja Mustanaamion HS.fi:stä. Luettavissa myös kaikki stripit vuodesta 2007. |

Viivi & Wagner - HS.fi www.hs.fi Parhaat stripit ja parisuhteen hoitovinkit. Viivi & Wagner -arkistosta löydät kaiken parisuhteesta sian ja naisen sanoin. Jaa parhaat st |

The Geomblog: Models for MapReduce feedproxy.google.com Models for MapReduce. I've been listening to Jeff Phillips' comparison of different models for MapReduce (he's teaching a class |

Free online dictionary definitions for learners of English ... www.oxfordadvancedlearnersdictionary.com Free online dictionary definitions and pronunciations for learners of English from the bestselling Oxford Advanced Learner's Dictionary. |