We announce

POSTDOC POSITIONS 

at the Institute of Informatics, University of Warsaw, Poland. The positions are supported by the ERC Consolidator Grant TUgbOAT: “Towards Unification of Algorithmic Tools” led by Piotr Sankowski.

The TUgbOAT’ focus is on basic algorithmic problems. Example topics include:

 * algorithms for finding matchings in graphs;

 * online algorithms in various settings;

 * studying and algorithmically exploiting properties of data.

The theoretical computer science group in Warsaw is strong and growing. Apart from the algorithms group members specializing in parameterized, approximation and graph algorithms (Łukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski), we have also a leading research group in logic and automata (Mikołaj Bojańczyk, Bartosz Klin, Sławomir Lasota).

We are looking for outstanding candidates with a Ph.D. (or soon to obtain a Ph.D.) in Computer Science or Mathematics who have already proven their high scientific potential in the area of algorithms or graph theory through publications in proceedings of highly ranked international conferences and/or journals. Background in the specific areas of projects in question will be an advantage.

The gross annual salary is around 100,000 PLN. For comparison, this translates to around twice the average salary in Poland. The position comes with generous travel support and no teaching duties. The application deadline is 15th March 2020. The default length of the contract is one year. The starting date is flexible.

To apply, send a CV to Piotr Sankowski <sank@mimuw.edu.pl>.

Questions and informal inquiries are welcome.

Here's an old trick that we found useful for proving some tight complexity lower bounds. You are given m coins, each of weight either a or b, and a modern scale that can tell you the total weight of any chosen subset of coins. How many weighings do you need to identify which coin is which? Checking each coin individually uses m weighings, but can you do less? In any weighing, we try some unknown number of weight-a coins between 0 and m, so this results in one of m + 1 possible values, giving us at most log(m + 1) bits of information. In total we need m bits of information to identify each coin, so clearly we will need at least Ω(m / log m) weighings. It turns out that this many is in fact enough, and this generalizes to various other settings with less restricted weights. This is the basis for two of our recent results: a tight complexity lower bound for Integer Linear Programming with few constraints and for multicoloring (a.k.a. b-fold coloring), assuming the Exponential Time Hypothesis. The trick allows us to use constraints that check the value of some number between 0 and m to indeed extract about log(m) bits of new information from each, in a way that is general enough to check m clauses of a 3-CNF-SAT instance using only O(m / log m) constraints. Continue reading →