If you are looking for an internship as a post doc in Poland, we encourage you to choose the University of Warsaw. Watch interviews with scientists from the Faculty of Mathematics, Informatics and Mechanics who are members of the ERC grant TUgbOAT research team. Find out what opportunities for professional and personal development are offered by working at the faculty.
Mateusz Rapicki, PhD (watch the wideo)
Michał Pawłowski, PhD student fellow (watch the video)
See what ERC grant postdocs say about their work at the University of Warsaw, Poland.
Mathieu Mari, PhD (France)
“I didn’t know anything about Poland in general. I found it would be a good adventure because I talked with my colleagues back in Paris and they told me that the University of Warsaw was one of the strongest place in Europe for computer science. I checked by myself and realised that it looks very interesting, so I accepted the offer and I came to the University.”
Runtian Ren, PhD (China)
“The Faculty of Informatics, Mathematics and Mechanics here in the University of Warsaw is very famous all around the world. If you are doing research related to computer science, you know this place for sure and also I know that Piotr is very famous on doing algorithmic research.“
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.
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:
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.
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.
Read moreSuppose 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 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.