It is still not too late to find a cheap flight to Warsaw. This includes Rome (see our suggestions in the previous email/post). We have a few unused slots for talks. Our plan is to open them to online participants who are students or postdocs. If you are a student or postdoc and want to give a talk remotely, via Zoom, please submit your title and abstract preferably by Monday via the registration form at https://ideas-ncbr.pl/en/wola/registration/ (If you have already registered, please register again.) If you have any time constraints, please indicate them at the beginning of the abstract (u ..read more

This is a reminder that the Workshop on Local Algorithms (WOLA) is taking place in Warsaw this year from June 25 to 27. It is conveniently scheduled right after STOC in Rome. Keynote speakers include Bernhard Haeupler, Rotem Oshman, Michael Kapralov, and Vincent Cohen-Addad. More information can be found on the official webpage: https://ideas-ncbr.pl/en/wola/ # Contributed talks and registration Apart from keynote talks, WOLA is going back to the pre-pandemic tradition of contributed talks by the workshop participants. **If you are planning to attend in person and want to give a talk**, please ..read more

We are excited to announce a new online seminar - IGAFIT Algorithmic Colloquium. This new event aims to integrate the European algorithmic community and keep it connected during the times of the pandemic. This online seminar will take place biweekly on Thursday at 14:00 CET, with the talks lasting for 45 minutes. Each talk will be followed by a networking and discussion session on topics related to the talk. We cordially invite all participants to this session. The meeting will be run on Airmeet. More details on the event can be found on IGAFIT web page. The first talk will be h ..read more

Years ago when I learned about Google PageRank algorithm, my first reaction was this is not the way it should be done! There should be some proof. This probably just shows that my CS education was too theoretical ;). Years later I have learned that indeed there are some nice tools to argue about the running time of PageRank algorithm. And very recently we were able to give some new parallel (in MPC model) algorithms for computing vanilla PageRank. We improved the number of rounds needed from O(log n) to O(log^2 log n) time. You can hear Solbodan talking out it here: https://www.youtube.com/wat ..read more

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 specializin ..read more

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; If you still hesitate, here are two interviews with former post-docs in ERC GRANT ..read more

5th Highlights of Algorithms conference (HALG 2020) ETH Zurich, June 3-5, 2020 ​ http://2020.highlightsofalgorithms.org/ The HALG 2020 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research. Similarly to previous years, there are two categories of invited talks: A. survey (60 minutes): a survey of an algorithmic topic that has seen exciting developments in last couple of years. B. paper (30 minutes): a significant algorithmic result appearing in a paper in 2019 or later. To nominate, please email halg2020.nomi ..read more

------------------------------------------------------------------- 4rd Highlights of Algorithms conference (HALG 2019) Copenhagen, June 14-16, 2019 http://highlightsofalgorithms.org/ The Highlights of Algorithms conference is a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of invited talks, as well as the possibility for all researchers and students to present their recent results through a series of short talk ..read more

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. Everything began in the haze of the 70's of the last millennium. It is nebulous who stumbled first upon this enigma. Some say th ..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? 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 ..read more