## Profile

Jukka Suomela
191 followers|189,889 views

## Stream

### Jukka Suomela

Shared publicly  -

Digital Humanities Hackathon in Helsinki: a five-day intensive course that brings together students and researchers of humanities, social sciences, and computer science.

#DigitalHumanities   #hackathon   #UniHelsinki   #Helsinki  ﻿
1
1

### Jukka Suomela

Shared publicly  -

Stefan Schmid, the new editor of the Distributed Computing Column of the Bulletin of the EATCS, asked me to write an article on the recent advances related to lower bounds for distributed graph algorithms. You can now read it in the February 2015 issue of the bulletin.

I decided to focus on two issues: symmetry breaking and local coordination. Symmetry breaking in this context is nowadays very well understood, but few people are even aware of the issue of local coordination.

If you ever wonder why I am so obsessed by the seemingly boring problem of finding maximal matchings in bipartite graphs, this article will hopefully gives an explanation.﻿
Thanks to the work of Kazuo Iwama, editor in chief of the bulletin, and of his collaborators, the February 2015 issue of the Bulletin of the EATCS is now available on line. You can download the whole issue in PDF from here, i...
2

### Jukka Suomela

Shared publicly  -

To our local students who have already got good skills in programming and algorithmic problem solving, and who are looking for new challenges:

Przemysław Uznański and Ari Korhonen are organising a special course for students who would be interested in taking part in international programming competitions. Registration deadline: 24 February.

#aalto   #competitiveprogramming  ﻿
T-106.6200 Special Course in Software Engineering: Introduction to Algorithmic Problem Solving and Programming Contests (3 cr). Course outline. This course is meant primarily for School of Science students with some Computer Science background. We are interested in following groups: ...
3
1

### Jukka Suomela

Shared publicly  -

In the context of traditional centralised algorithms, it does not usually make much sense to discuss the exact time complexity of a problem (without hiding anything in O-notation); the constants depend too much on the precise model of computing. However, in distributed computing, the exact running time of an algorithm is well-defined; it is simply defined to be equal to the number of communication rounds, and this is a fairly universal quantity that is independent of the precise details of the model of computing.

In this work we study the exact distributed time complexity of a very classical problem: colouring directed paths with 3 colours. It is very well known (thanks to the classical results by Cole and Vishkin and Linial from the 1980s–1990s) that the time complexity is roughly 0.5 log*(n) ± some constants. In this work we get rid of the "± some constants" part — it turns out that for infinitely many values of n, the time complexity is exactly 0.5 log*(n).

One of the parts that I like most is that in this work we use computational techniques not only to prove better upper bounds, but also to prove better lower bounds. We can nowadays outsource more and more of our work to computers.

#distributedcomputing   #distributedalgorithms   #graphcoloring  ﻿
Abstract: We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with $n$ colours, by prior work it is known that we can find a proper 3-colouring in $\frac{1}{2} \log^*(n) \pm O(1)$ communication rounds.
2

### Jukka Suomela

Shared publicly  -

HSTS is a nice idea, but why can't the browsers provide a decent user interface for controlling it?

If I accidentally browse an https site and want to get back to the http site, why can't I do it easily?﻿
HTTP Strict Transport Security (HSTS) is a web security policy mechanism which is necessary to protect secure HTTPS websites against downgrade attacks, and which greatly simplifies protection against cookie hijacking. It allows web servers to declare that web browsers (or other complying user ...
1

### Jukka Suomela

Shared publicly  -

"As our way of saying thanks for completing the checkup by 17 February 2015, we’ll give you a permanent 2 gigabyte bump in your Google Drive storage plan."﻿
4
2
In their circles
129 people
Have them in circles
191 people

### Jukka Suomela

Shared publicly  -

Most of Scandinavia determines fines based on income. Could such a system work in the U.S.?
View original post
1
1

### Jukka Suomela

Shared publicly  -

"Unfortunately, we weren’t able to prove its correctness. A closer analysis showed that this was, quite simply, because TimSort was broken and our theoretical considerations finally led us to a path towards finding the bug (interestingly, that bug appears already in the Python implementation)."

#timsort   #java   #python  ﻿
7
6

do u have idea how to use python packages?﻿

### Jukka Suomela

Shared publicly  -

"The IESG has formally approved the HTTP/2 and HPACK specifications".

HTTP/2: "… introducing header field compression and allowing multiple concurrent exchanges on the same connection …" — https://tools.ietf.org/html/draft-ietf-httpbis-http2-17

HPACK: "… compression format for efficiently representing HTTP header fields …" — https://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12

#http2   #hpack  ﻿
2

### Jukka Suomela

Shared publicly  -

In load balancing, people are usually looking for globally optimal or near-optimal solutions. However, in a distributed setting, finding such a solution necessarily takes linear-in-n communication rounds in a graph with n nodes (consider, for example, a long path).

In this work, we had a look at a much simpler task: finding a locally optimal solution, i.e., a solution in which the loads of adjacent nodes differ by at most 1. This can be seen as a game-theoretic equilibrium (the edges are selfish agents that try to move load between their endpoints to minimise their makespan). This problem has also a nice physical analogue (we want to collapse the piles of the load tokens so that the system is stable; all slopes are at most 45°). And this problem can be seen as a generalisation of smoothing with moving averages (from fractional to discrete smoothing, and from paths to graphs).

It turned out that the load balancing problem can be solved with a deterministic distributed algorithm very efficiently: the number of communication rounds only depends on the maximum load and the maximum degree, and it is independent of the number of nodes. Put otherwise, if the maximum degree and maximum load are bounded by constants, the problem can be solved in constant time, even in infinitely large graphs.

Here is the ArXiv manuscript: http://arxiv.org/abs/1502.04511 — we did most of this work while Laurent Feuilloley was on his "pre-doc" visit in our group. And here is a JavaScript toy for one special case: http://users.ics.aalto.fi/suomela/load-balancing-demo/

Abstract: This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree $\Delta$, and each node has up to $L$ units of load. The task is to distribute the load more evenly so that the loads of adjacent nodes differ by at most $1$.
3
1

### Jukka Suomela

Shared publicly  -

The PODC 2015 web site has been a victim of a denial-of-service attack. Apologies for the difficulties.

We have extended the deadline by 2 days. The new submission deadline is: February 12, 2015, at 23:59 HAST (Honolulu, Hawaii time).

Even if you have difficulties reaching the PODC web site, you can
still submit your paper using EasyChair as usual. The submission site is: https://easychair.org/conferences/?conf=podc2015

See the CFP for the submission instructions: http://dmatheorynet.blogspot.com/2015/02/dmanet-podc-2015-call-for-papers.html

#PODC2015Spain﻿
1 comment on original post
1

### Jukka Suomela

Announcements  -

The PODC 2015 web site has been a victim of a denial-of-service attack. Apologies for the difficulties.

We have extended the deadline by 2 days. The new submission deadline is: February 12, 2015, at 23:59 HAST (Honolulu, Hawaii time).

Even if you have difficulties reaching the PODC web site, you can still submit your paper using EasyChair as usual. The submission site is: https://easychair.org/conferences/?conf=podc2015

See the CFP for the submission instructions: http://dmatheorynet.blogspot.com/2015/02/dmanet-podc-2015-call-for-papers.html

#PODC2015Spain﻿
1
3

Quite ironical :-(﻿
People
In their circles
129 people
Have them in circles
191 people
Contributor to
Work
Occupation
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 | WIREDwww.wired.comComputer 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 Blogsblogs.atlassian.comGit 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 2014processalgebra.blogspot.comThe 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.comNews on barcode software, 2D bar code software, Bluetooth, Auto-ID, RFID, AIDC, barcode labeling, reporting software, data acquisition and s
 Movesmarket.android.comMoves automatically tracks your everyday life and exercise. Just carry your phone in your pocket or bag. FEATURES • Automatic Tracking: Reco
 Google Play Книгиmarket.android.comGoogle Play – это настоящий рай для книголюбов. В этом интернет-магазине вас ждут миллионы книг, в том числе бесплатных. Выберите из новинок
 GPS Testmarket.android.comThe 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 Musicmarket.android.comGoogle 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. RSSmarket.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,
 Dropboxmarket.android.comDropbox 提供免費的服務，讓您可以隨時隨地存取您所有的相片、文件和影片。一旦在電腦上安裝了 Dropbox，您儲存在 Dropbox 的任何檔案都會自動儲存到您所有的電腦、手機及 Dropbox 網站。有了 Dropbox 應用程式，您可以把重要的東西全部帶著走。即使是出門
 Andropas Promarket.android.comAndropas Pro lisää uusia ominaisuuksia Andropas-ohjelmaan. Tue Andropaksen kehitystä ja osta Andropas Pro.Ominaisuudet: - Suosikkipysäkit ja
 younited by F-Securemarket.android.comWith 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 networkgowers.wordpress.comThis 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 Talkwww.abstract-talk.orgAbstract. 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.orgThe On-Line Encyclopedia of Integer Sequences™ (OEIS™). Enter a sequence, word, or sequence number: Hints. Note: Advanced searches are now m
 ACM Digital Libraryportal.acm.orgwww.acm.org - The premier society in computing brings you the Computer Portal.
 Fingerpori - HS.fiwww.hs.fiLöydät Fingerporin Heimon, Allanin ja Mustanaamion HS.fi:stä. Luettavissa myös kaikki stripit vuodesta 2007.
 Viivi & Wagner - HS.fiwww.hs.fiParhaat stripit ja parisuhteen hoitovinkit. Viivi & Wagner -arkistosta löydät kaiken parisuhteesta sian ja naisen sanoin. Jaa parhaat st
 The Geomblog: Models for MapReducefeedproxy.google.comModels 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.comFree online dictionary definitions and pronunciations for learners of English from the bestselling Oxford Advanced Learner's Dictionary.