Cover photo
Jukka Suomela
205 followers|220,147 views


Jukka Suomela

Shared publicly  - 
This is 2015.
Sony announces end of production of Betamax cassettes for March next year, 40 years after its introduction and 28 years after losing format war to VHS
Chen Avin's profile photo
Cool read. Bring memories... 
Add a comment...

Jukka Suomela

Shared publicly  - 
Here is a paper that we just submitted to ArXiv:

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  
Abstract: We show that any randomised Monte Carlo distributed algorithm for the Lov\'asz local lemma requires $\Omega(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where $d$ is the ...
Add a comment...

Jukka Suomela

Shared publicly  - 
I was recently elected as one of the new members of the EATCS 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:

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  
Shantanu Sharma's profile photo
Congrats :)
Add a comment...

Jukka Suomela

Shared publicly  - 
STOC 2016 submission #300.
Add a comment...

Jukka Suomela

Shared publicly  - 
In honour of Boole's 200th, here's his episode in the Thrilling Adventures! 1. Boole is someone I've shamefully neglected making fun of in this comic. He was a rather obscure professor of mathemati...
Add a comment...

Jukka Suomela

Shared publicly  - 
This might actually be convenient.

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.
Add a comment...
In their circles
137 people
Have them in circles
205 people
Luca Aceto's profile photo
Ram Krishn Mishra's profile photo
Suzan Bayhan's profile photo
Robin Partanen's profile photo
Toni Ruottu's profile photo
Iivari Äikäs's profile photo
Akinori Kawachi's profile photo
Heikki Arponen's profile photo
anibal gil's profile photo

Jukka Suomela

Shared publicly  - 
Member poll on the establishment of an open access journal of the EATCS!

#openaccess   #eatcs   #tcs  
Add a comment...

Jukka Suomela

Shared publicly  - 
As rumors go, this (quasipolynomial time for graph isomorphism, improving Babai and Luks 1983 exponential in the square root of n) seems like a pretty big one.
Next Tuesday, a week from today, Laci Babai will talk at the University of Chicago about a new algorithm that solves graph isomorphism in quasipolynomial time. There should also be a follow-up talk...
View original post
Add a comment...

Jukka Suomela

Shared publicly  - 
Today, SWAT signs contract with Dagstuhl for publishing its proceedings in LIPIcs for the next five years
View original post
Add a comment...

Jukka Suomela

Shared publicly  - 
Fortunately Nexus 5X is coming, no need to suffer from OEM Androids.

#nexus5x   #android  
Mobe-makers just can't be bothered keeping Google-spawn up to date
Add a comment...

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

Call for papers: — submission deadline 12 February 2016

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  
View original post
Sajin Koroth's profile photo
Add a comment...
Assistant Professor
Jukka Suomela's +1's are the things they like, agree with, or want to recommend.
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

Best paper awards at ICALP 2014

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

News on barcode software, 2D bar code software, Bluetooth, Auto-ID, RFID, AIDC, barcode labeling, reporting software, data acquisition and s


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

Google Play Книги

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

GPS Test

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

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

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

Andropas Pro

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

younited by F-Secure

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

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

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

ACM Digital Library - The premier society in computing brings you the Computer Portal.

Fingerpori -

Löydät Fingerporin Heimon, Allanin ja Mustanaamionä. Luettavissa myös kaikki stripit vuodesta 2007.

Viivi & Wagner -

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

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

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