### Jukka Suomela

Shared publicly -#DigitalHumanities #hackathon #UniHelsinki #Helsinki

Start a hangout

Jukka Suomela

191 followers|189,889 views

AboutPostsPhotos+1's

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

#DigitalHumanities #hackathon #UniHelsinki #Helsinki

1

1

Add a comment...

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.

I decided to focus on two issues:

If you ever wonder why I am so obsessed by the seemingly boring problem of finding

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

Add a comment...

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

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:

#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

Add a comment...

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

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

#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

Add a comment...

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?

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

Add a comment...

"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

Add a comment...

In their circles

129 people

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

1

1

Add a comment...

"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

#timsort #java #python

7

6

do u have idea how to use python packages?

Add a comment...

"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

HTTP/2: "… introducing

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

#http2 #hpack

2

Add a comment...

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/

#distributedalgorithms #loadbalancing

In this work, we had a look at a much simpler task: finding a

It turned out that the load balancing problem

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/

#distributedalgorithms #loadbalancing

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

Add a comment...

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

You can find the latest updates also by following us on Twitter: https://twitter.com/@podc_conference

#PODC2015Spain

We have extended the deadline by 2 days. The new submission deadline is:

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

You can find the latest updates also by following us on Twitter: https://twitter.com/@podc_conference

#PODC2015Spain

1

Add a comment...

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

You can find the latest updates also by following us on Twitter: https://twitter.com/@podc_conference

#PODC2015Spain

We have extended the deadline by 2 days. The new submission deadline is:

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

You can find the latest updates also by following us on Twitter: https://twitter.com/@podc_conference

#PODC2015Spain

1

3

Moshe Vardi

+

2

3

2

3

2

Quite ironical :-(

Add a comment...

People

In their circles

129 people

Links

YouTube

Contributor to

- aalto.fi (current)

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