If you are interested in machine learning and artificial intelligence but you are not convinced to work in Poland watch an interview with Jakub Pawlewicz (Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland).

## Is working at the Institute of Informatics attractive for a foreigner scientist?

This and many other questions are answered by Anish Mukherjee (India), post-doctoral fellow in ERC TUgbOAT grant of prof. Piotr Sankowski.

Watch an interview and find out how the participation in ERC grant can help to meet scientific, professional and personal goals.

## Postdoc position in theoretical computer science

We announce

**POSTDOCTORAL POSITIONS IN MACHINE LEARNING **

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

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

Questions and informal inquiries are welcome.

## We are looking for YOU to join our award-winning scientific team!

Have you just graduated your PhD and are considering a post-doc position in theory of informatics? Science is your passion and you would like to spend most of your post-doc researching on whatever interests you? You are in the right place.

At MIM UW we offer you:

- Great FREEDOM OF CHOICE related to what to work on;
- Just A FEW or NO teaching duties;
- A lot of TIME FOR RESEARCH;
- Chance to cooperate with VERY EXPERIENCED and TALENTED scientists;
- FRIENDLY environment;
- Excellent SUPPORT from our administrative staff;

**Krzysztof Fleszar**and find out how participation in the ERC GRANT has changed his life.

**Adam Karczmarz**told us about his experience as a post-doc at the Faculty of Mathematics, Informatics and Mechanics, University of Warsaw in ERC GRANT.

## The Curse of Euclidean Metric: Square Roots

The deadline was approaching without mercy and there was, of course, still some polishing to be done for our SODA paper. But then we run into an issue. To make things worse, this issue turned out to be a hard one, a fundamental known open problem in computational geometry. The good thing is, I liked the problem so much that I decided to dedicate it this post. This is the story about the Sum of Square Roots problem and how we bypassed (ignored) it without solving it.

## How to identify m numbers using m/log m checks

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?

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.

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.

## Prophet inequality and auction design

Suppose you want to sell a car and there are 10 agents willing to buy it. You are not sure how much they could pay but for each of them you know a probability distribution of how high the offer will be. For example, a car salon would always pay 10K but some person might offer 5Kor 15K with equal probability. The best you could do is to first negotiate with all of them and then pick the highest bid. Unfortunately, you cannot do so – after seeing each offer you must irrevocably choose either to sell the car or to refuse the offer. What is the best strategy to maximize your revenue in this case?

## The streaming k-mismatch problem

The central problem of text processing is pattern matching: given two strings (a pattern and a text), find all fragments of the text matching the pattern. In exact matching, solely equal strings match; however, this condition is relaxed in many variants of approximate pattern matching. In the k-mismatch problem, we allow for up to k substitutions, that is, strings of the same length are assumed to match even if there are at most k mismatching characters between them.

## A Subquadratic Approximation Scheme for Partition

The** Subset Sum** problem is one of the most fundamental problem in theoretical computer science. One is given a set *S* of *n* integers and an integer* t*. The problem is to determine if there exists a subset of *S* with total sum equal exactly *t*.