Author: Renata Czarniecka

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

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.

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.

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.

Read more

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.

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? 

Read more