Profile

Cover photo
Jukka Suomela
191 followers|189,889 views
AboutPostsPhotos+1's

Stream

 
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
Joel Rybicki's profile photo
Add a comment...

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
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  
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
Claudio Omar Biale's profile photo
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  
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...

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
Add a comment...

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
Antti Vanne's profile photoSajin Koroth's profile photo
Add a comment...
In their circles
129 people
Have them in circles
191 people
Jouni Sirén's profile photo
Ella Peltonen's profile photo
Sylvain Soliman's profile photo
Esa Pitkänen's profile photo
Alessandro Panconesi's profile photo
Pat Morin's profile photo
Keller Barbara's profile photo
Nelka Arosha's profile photo
Jara Uitto's profile photo

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
Jari Juslin's profile photo
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  
7
6
Андрей Рогачёв's profile photoPéter Erben's profile photoStefan Huber's profile photoEd S's profile photo
 
do u have idea how to use python packages?
Add a comment...

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
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  
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
Claudio Omar Biale's profile photo
Add a comment...

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

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

#PODC2015Spain
1 comment on original post
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
1
3
Moshe Vardi's profile photoJukka Suomela's profile photoSajin Koroth's profile photoAdam Smith's profile photo
 
Quite ironical :-(
Add a comment...
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.