Mikołaj Bojańczyk
March 4, 2016

Positions (deadline April 30, 2016)

Below is a call whose deadline has elapsed. I will do a new call at the end of 2016.

I am starting an ERC Consolidator grant on automata and logic. The project is called “A unified theory of finite-state recognisability”, and its main goal is to find algebraic structures (like monoids) for things like infinite trees or profinite words. However, I can be very flexible on the topic, as long as it is tangentially connected to logic or automata.

I am searching for talented postdocs and phd students. The deadline for applications is April 30, 2016. Send applications to me by email. Please feel to ask questions before that date!

The topic is automata and logic, and I am flexible on the choice of subtopic.

Postdocs. The postdoc can begin at any time from June 1 until the end of 2016. The duration is 6 – 12 months, with a possibility of extension for another year. The application consists of your name and 1-2 names of people who can provide references. I am looking for people with a good track record in the top conferences of the field. Teaching is optional.

PhD students. A typical duration is 4 years, starting any time from June 1 until the end of 2016. In application please include a cv and 1-2 names of people who can provide references. I am looking for candidates with a strong background in mathematics.

August 11, 2015

Tree width à la metro

Here is a way of drawing graphs of bounded tree width, inspired by metro maps. The horizontal black lines are graph edges, the coloured shapes are vertices, and the gray background is the tree underlying the decomposition.



The mathematical content of the picture is that a graph has tree width k if and only if it is a subgraph of a (k+1)-colourable chordal graph (thanks to Michał Pilipczuk for pointing this out).

June 20, 2015

EATCS council

In 2013, I joined the EATCS council. Here is what I promised to do:


I am a candidate for the EATCS council. My program consists of three items. The first item is something where I promise concrete action, the remaining two are more speculative.

  1. I will support open access, in particular for ICALP proceedings.
  2. In the long term, I think that the TCS community should move from publishing in conferences to publishing in journals. The ensuing travel is a waste of time and money. It is not clear to me how the EATCS can help solve this problem right now, without losing the accumulated prestige capital of ICALP. Maybe ICALP could move to a continuous submission model like VLDB?
  3. It is my impression that the current EATCS members are mainly people who have recently attended ICALP, which is a bit random. Membership should be made more representative. Maybe we should make membership free (but still feed EATCS from an ICALP tax)?


Update. The first item is solved: starting with 2016, ICALP will be using the open access LIPICS system. As it turned out, this idea had overwhelming support inside the council.