Profile cover photo
Profile photo
Jukka Suomela
226 followers
226 followers
About
Posts

Post has attachment
PODC/DISC research community in the past 10 years.

In this figure, there is a connection between two persons if they are strongly associated in the following sense:

· they have many joint PODC or DISC papers, or
· their work has often been presented in the same session.

This only includes authors with sufficiently many publications and at least one sufficiently strong connection to someone else. So if you publish often in PODC/DISC but with a diverse set of coauthors or on varying topics, you probably won't find your name here — apologies in advance, this is a rather crude approximation of the community! To put yourself on the map, see if you can find your coauthors in one cluster.

Inside each cluster, the authors are simply ordered alphabetically. The size of a node is proportional to the number of PODC/DISC papers in the past 10 years. The text labels around each cluster contain typical session titles and typical words that appear in the titles of their papers.

The data is extracted from DBLP (papers) and from PODC and DISC programs (sessions). Especially the information on sessions is noisy.

PDF version here: https://users.ics.aalto.fi/suomela/podc-disc/podc-disc.pdf
Photo
Add a comment...

Two new manuscripts on arXiv today:

[1] "The distributed complexity of locally checkable problems on paths is decidable" — with Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie: https://arxiv.org/abs/1811.01672

[2] "Hardness of minimal symmetry breaking in distributed computing" — with Alkida Balliu, Juho Hirvonen, Dennis Olivetti: https://arxiv.org/abs/1811.01643

Both of these are related to the research program that aims at understanding the distributed computational complexity of locally checkable problems.

Here we have a graph problem in which a feasible solution is easy to verify: if the solution looks good in all local neighborhoods, then it is also globally feasible.

But how easy it is to find a feasible solution for a given problem? Can we find a solution so that each node only looks at its own local neighborhood in the graph, or do we necessarily need global information on the entire graph?

———

BACKGROUND

Let us have a look at the simple special case of cycles without any input labels. The task is to label the nodes with output labels from some constant-size set, subject to some local constraints — formally, we have an LCL problem in a cycle. Now all such problems fall in one of the following classes:

(a) The problem is trivial to solve in constant time. We can label the entire cycle with some constant label, e.g.:

…111111111111…

(b) The problem is nontrivial but can be solved without global coordination. There is always some flexibility in the constraints; you can fix the solution in distant parts of the graph without e.g. knowing the exact distance between them. A good example is the task of finding a maximal independent set:

…001010010100…

(c) The problem requires global coordination (and, depending on the length of the cycle, it may not be solvable at all). There is no flexibility; fix the solution in one part of the network and nodes arbitrarily far from it have to agree on the choice. A good example is the task of finding a proper 2-coloring:

…121212121212…

From the perspective of the LOCAL model of distributed computing, problems of type (a) are solvable in O(1) communication rounds, problems of type (b) require Θ(log* n) rounds, and problems of type (c) require Θ(n) rounds. Here the details of the model of computing do not matter much; the same holds e.g. for both deterministic algorithms (assuming unique identifiers) and for randomized algorithms (with or without unique identifiers).

A key observation here is that there are gaps in the complexity spectrum: there is no LCL problem that would have a complexity of e.g. Θ(log n) rounds in cycles. As soon as you have an algorithm that solves an LCL in o(n) rounds, you can speed it up to O(log* n) rounds.

Also, all of the above is decidable: given the description of an LCL problem, we can automatically (and easily) tell whether it is of type (a), (b), or (c).

———

NEW RESULTS

Now what happens when we step beyond the fully-understood special case of unlabeled cycles?

Paper [1] looks at how far we can push the boundary of decidability beyond unlabeled cycles. It is known that e.g. LCLs on 2-dimensional grids are not decidable. We conjecture that LCLs on trees (and maybe also bounded-treewidth graphs) are decidable, but the first obstacle here is related to input labels. In essence, the structure of the tree can be used to encode input labels, and hence to have any hope of understanding trees, we need to first understand what happens in paths or cycles with with input labels. We show that this case is indeed decidable — but much more difficult than the case of unlabeled cycles.

Paper [2] looks at the classification of LCLs on trees. In cycles it was known that there is nothing between ω(1) and o(log* n), but for trees this has remained open, despite numerous recent results related to the landscape of the distributed complexity of LCL problems. The general case is still open, but we look at homogeneous LCLs that are, in essence, problems that are interesting in the middle of a regular tree or a regular high-girth graph. We show that there are no homogeneous LCLs with complexities between ω(1) and o(log* n). The key idea is this: we identify a minimal nontrivial homogeneous LCL: weak 2-coloring. We show that if we can solve any nontrivial homogeneous LCL in time T, we can also solve weak 2-coloring in time O(T). Then we prove that weak 2-coloring requires Ω(log* n), even if we are in a very friendly setting of a regular, consistently oriented tree.
Add a comment...

Post has attachment

Post has attachment
All presentation slides from ADGA 2018 are now available online: http://adga.hiit.fi/2018/

Many thanks to Merav for chairing the workshop, and to all speakers for the great talks!

ADGA will be organized again next year, co-located with DISC 2019 in Budapest.
Add a comment...

Post has attachment
DISC 2018 is now over, lots of interesting talks!

I'll be the PC chair of DISC 2019 — if you have any suggestions regarding the program or the reviewing process, please let me know!

One big challenge: DISC is growing, there are more and more good submissions, and in the recent years good papers have been rejected because there simply isn't room for more talks without changing the format of the conference. One possibility would be to introduce parallel sessions.

Another new idea that was discussed in the business meeting is switching to a double-blind review process. This would be a big change and I'd be interested to hear more about possible new challenges we would need to take into account in the work of the PC.
Add a comment...

Post has attachment
The computational complexity landscape of LCL problems in the LOCAL model:
· blue = LCL problem
· orange = gap

Diagram as a PDF file: https://users.ics.aalto.fi/suomela/lcl-landscape/graphs.pdf

The same thing for trees: https://users.ics.aalto.fi/suomela/lcl-landscape/trees.pdf
Photo
Add a comment...

Post has attachment
Who is the leading theoretical computer scientist under 35?

Nominate them for the Presburger Award 2019 now!

Please do not assume that everyone knows that X is the leading young researcher at the moment so of course they will be considered — someone has to submit a nomination for them. :)

Previous winners:

· 2010: Mikolaj Bojanczyk
· 2011: Patricia Bouyer-Decitre
· 2012: Venkatesan Guruswami
· 2012: Mihai Patrascu
· 2013: Erik Demaine
· 2014: David Woodruff
· 2015: Xi Chen
· 2016: Mark Braverman
· 2017: Alexandra Silva
· 2018: Aleksander Madry

More information: http://eatcs.org/index.php/presburger

Nomination deadline: 31 December 2018

If you have any questions on the award or the nomination process, please feel free to ask me! I am chairing the award committee this year.

Post has attachment
Who is the leading theoretical computer scientist under 35?

Nominate them for the Presburger Award 2019 now!

Please do not assume that everyone knows that X is the leading young researcher at the moment so of course they will be considered — someone has to submit a nomination for them. :)

Previous winners:

· 2010: Mikolaj Bojanczyk
· 2011: Patricia Bouyer-Decitre
· 2012: Venkatesan Guruswami
· 2012: Mihai Patrascu
· 2013: Erik Demaine
· 2014: David Woodruff
· 2015: Xi Chen
· 2016: Mark Braverman
· 2017: Alexandra Silva
· 2018: Aleksander Madry

More information: http://eatcs.org/index.php/presburger

Nomination deadline: 31 December 2018

If you have any questions on the award or the nomination process, please feel free to ask me! I am chairing the award committee this year.
Add a comment...

Post has attachment
Where to find me after Google+ shuts down:

· Twitter — mostly research-related posts in English: https://twitter.com/JukkaSuomela

· Facebook — mostly something completely different: https://www.facebook.com/jukka.suomela

· Instragram: https://www.instagram.com/jukka.suomela/
Add a comment...

Post has attachment
Claire Mathieu talking about a distributed real-world implementation of Gale–Shapley that is running in France. The nodes on one side are represented by a central computer that knows all the rankings on that side, but the nodes on the other side are actual human beings who do not need to reveal their rankings. One communication round takes a few days, and the system is asynchronous.
Add a comment...
Wait while more posts are being loaded