Call for Participation: HALG 2019 (Highlights of Algorithms)

4rd Highlights of Algorithms conference (HALG 2019)
Copenhagen, June 14-16, 2019

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
talks and poster presentations. Attending the Highlights of Algorithms
conference will also be an opportunity for networking and meeting
leading researchers in algorithms.


The conference will begin on Friday, June 14, at 9:00 and end on
Sunday, June 16, at 18:00. A detailed schedule and a list of all
accepted short contributions can be found at:



Please register on our webpage
We have done our best to keep registration fees at a minimum:

Early registration (by April 29, 2019)
- academic rate (incl. postdocs): 160€
- student rate: 115€

Regular registration will be 50€ more expensive.

The organizers strongly recommend that you book your hotel as soon as possible.



The conference will take place at the H.C. Ørsted Institute of the
University of Copenhagen.
The address is: Universitetsparken 5, DK-2100 Copenhagen.



Survey speakers:
Monika Henzinger (University of Vienna)
Thomas Vidick (California Institute of Technology)
Laszlo Vegh (London School of Economics)
James Lee (University of Washington)
Timothy Chan (University of Illinois at Urbana-Champaign)
Sergei Vassilvitskii (Google, New York)

Invited talks:
Martin Grohe (RWTH Aachen University)
Josh Alman (MIT)
Nima Anari (Stanford University)
Michal Koucký (Charles University)
Naveen Garg (IIT Delhi)
Vera Traub (University of Bonn)
Rico Zenklusen (ETH Zurich)
Shayan Oveis Gharan (University of Washington)
Greg Bodwin (MIT)
Cliff Stein (Columbia University)
Sungjin Im (University of California at Merced)
C. Seshadhriy (University of California, Santa Cruz)
Shay Moran (Technion)
Bundit Laekhanukit (Shanghai University of Finance and Economics)
Sebastien Bubeck (Microsoft Research, Redmond)
Sushant Sachdeva (University of Toronto)
Kunal Talwar (Google Brain)
Moses Charikar (Stanford University)
Shuichi Hirahara (University of Tokyo)


The Curse of Euclidean Metric: Square Roots

The Curse of Metric Island

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 that Ron Graham has discussed the problem in public lectures, some others say that Joseph O'Rourke has posed it as an open question in the American Mathematical Monthly, while some others suspect that the problem had been already hiding in older different formulations. However, it is a historical fact that one shinny/cloudy day, three computer scientists finished polishing a manuscript that became a classical paper known as "Some NP-complete geometric problems". In this paper, Michael Garey, Ron Graham and David Johnson showed the NP-hardness of two important problems in geometric metrics: Steiner Tree and Traveling Salesman. For the Euclidean plane, they showed only NP-hardness as they did not manage to show that these problems are contained in NP. Moreover, they accentuated that we cannot even rule out that the decision version of Euclidean Minimum Spanning Tree is outside of NP. What a seeming paradox given that we can compute such a minimum tree in polynomial time! So, whom did they blame? The short answer: The Euclidean metric. Garey and his coauthors explain that all these problems have a common hidden issue: They rely on comparing Euclidean lengths, that is, they rely on comparing irrational numbers based on square roots. Whereas this task is trivial if we just want to compare two line segments (e.g. by comparing the radicands), the problem starts when we want to compare two polygonal paths. Even assuming rational (or, after scaling, integer) coordinates, this problem translates into a question that is fundamental in computational geometry: Given two lists of integers, a1 ... and b1 ..., can we decide whether "∑ √ai ≥ ∑ √bi" in P? Put into words: Can we efficiently compare two sums of square roots over integers?

Continue reading

HALG 2019 - Call For Submissions of Short Contributed Presentations

The HALG 2019 conference seeks submissions for contributed presentations. Each presentation is expected to consist of a poster and a short talk (an invitation to the poster). There will be no conference proceedings, hence presenting work already published at a different venue or journal (or to be submitted there) is welcome.

If you would like to present your results at HALG 2019, please submit their details the abstract of the talk or the contribution of the poster via EasyChair:

The abstract should include (when relevant) information where the results have been published/accepted (e.g., conference), and where they are publicly available (e.g., arXiv). All submissions will be reviewed by the program committee, giving priority to new work not formally published yet, and to papers published in 2018 or later.

Submissions deadline: March 15th, 2019.
Late submissions will be accepted subject to space constraints.

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 5K or 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?

In turns out that this is a well-studied optimization problem with a simple strategy that guarantees you can (on expectation) earn at least half as much as a hypothetical prophet, who knows all the bids in advance. This result is known as the prophet inequality. What is more surprising, this strategy would work even if you are a car retailer and want to sell five cars. Moreover, you might want to have some constraints, for example you do not want to sell two cars to buyers from the same city, or have multiple kinds of cars with different evaluations, and you can always guarantee an expected revenue comparable to the one of the prophets.

This problem not only exploits beautiful math but also has important applications in internet ad display. Actually, whenever you type a query into a web search engine, the ad system performs this kind of car-selling game with the ad suppliers, who offer different bids for their ad to be displayed to you.

Here is a link to our recent work with new developments in this theory:

Michał Włodarczyk

Call for Nominations - HALG 2019

Call for Nominations

 4th Highlights of Algorithms conference (HALG 2019)

Copenhagen, June 14-16, 2019

The HALG 2019 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

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 2018 or later.

 To nominate, please email  the
following information:

1. Basic details: speaker name + topic (for survey talk) or paper’s
title, authors, conference/arxiv + preferable speaker (for paper

2. Brief justification: Focus on the benefits to the audience, e.g.,
quality of results, importance/relevance of topic, clarity of talk,
speaker’s presentation skills.

All nominations will be reviewed by the Program Committee (PC) to
select speakers that will be invited to the conference.

Nominations deadline: December 9, 2018 (for full consideration).

Please keep in mind that the conference does not provide financial
support for the speakers.

MIM UW – great place to work!

Interview with Lucas Pastor, former Postdoc at MIM UW, Warsaw, Poland


Renata Czarniecka: - What made you choose the Institute of Informatics at University of Warsaw (MIM UW ) for your postdoc?

Lukas Pastor: - I found out about MIM UW from my friend, who is a researcher in my field. She told me that prof. Marcin Pilipczuk and his team from MIM UW are very renowned in the field and very nice people. So I decided to apply for the postdoc position. I sent an email with my postdoc research project and CV and then I was asked for a Skype interview. After the interview, Marcin told me that I got the position. I found Marcin and his brother Michał Pilipczuk very kind, open-minded people, and of very strong in mathematics in general.

What advice would you give for future postdocs at MIM UW?

- MIM UW is a great environment for a postdoc, with highly skilled and talented researchers. Do not hesitate to ask around who would be interested in working with you. You will find many research mates!

What have you gained from your postdoc?

- I’ve learned a lot of things thanks to my postdoc. Marcin and  the people I worked with during my stay, shared many different things with me that strengthened my knowledge in the area of the Erdős-Hajnal conjecture. The most important were the proof techniques around this conjecture. I was struck by the fact that each of those results are impressive, clever and yet so little is known about this famous problem.

What’s the potential impact of your work?

- It is hard to tell. We tried very hard and got very little advances but we all learned from this work. Furthermore, I had the opportunity to work with a French PhD student, Marc Heinrich, that made a research visit in MIM UW. It was really extraordinary experience. Together we developed a parameterized algorithms for a graph optimization problem.

What is your direct goal right now?

- My direct goal right now is to give high quality lectures, tutorials and practical work to my students and go deep into my research topics.

What are your plans for the future?

- I would like to tackle some well-known, difficult and complex problems in graph theory with different people, including Marcin and the people I’ve worked with at MIM UW! I would like to try to solve some list-coloring problems. List-coloring problems are very hard and each result, even the smallest, needed hard work. Related to this kind of problems, I would also like to try to attack coloring problems in structured graphs, more precisely, graphs not containing long induced paths.

What makes MIM UW a great place to work?

- MIM UW is a great place to work because of high scientific level. Beside this everybody I’ve met here was very humble and happy to work with a young researcher such as myself. I also appreciate the help provided by the administrative staff at MIM UW. All of them were extremely helpful. In particular Ms. Ewa Puchalska who was super kind and supportive. She even helped me with things not directly related to MIM UW administration, such as renting a flat. Great thing of working at MIM UW was that there was no language barrier. Everybody at the faculty speaks fluent English, especially young people.

How did you find Warsaw as a place to live in?

-Warsaw is an interesting city. There is a lot of nice places  to go out for a drink or eat. I was surprised by the good quality to price ratio in most of the restaurants I went to. Public transport in Warsaw is really well-organized so it was easy to travel around Warsaw thanks to the trams, buses and metro lines. Furthermore, Warsaw is a very safe city, even at night. All the things mentioned above make it a great city to live in for a young foreigner.



Lucas Pastor obtained his PhD in Grenoble under the supervision of Frédéric Maffray and Sylvain Gravier. His research interests focus mostly on graph theory, more precisely structural graph theory and optimization problems in graphs.


During the period from December 2017 to August 2018 he attended a one-year fellowship (postdoc position) at the Institute of Informatics, University of Warsaw, Poland. The position was supported by the ERC Starting Grant CUTACOMBS: “Cuts and decompositions: algorithms and combinatorial properties” led by prof. Marcin Pilipczuk.


HALG 2019 in Copenhagen on June 14-16, 2019

I was recently asked to chair the 4th Highlights of Algorithms conference (HALG 2019). HALG 2019 will be held in Copenhagen on June 14-16, 2019. First, I wish to see many of you there. HALG works very well and for me it was one of the best algorithmic conferences I attended in recent years. You can read more in a report in EATCS  bulletin. Second, I hope we will have a great program thanks to the help of the following people in the PC:

Susanne Albers (Technical University of Munich)
Edith Cohen  (Google & Tel Aviv University)
Shiri Chechik (Tel Aviv University)
Fabian Kuhn (University of Freiburg)
Seffi Naor (Technion)
Marcin Pilipczuk (University of Warsaw)
Piotr Sankowski (chair - University of Warsaw)
David Shmoys (Cornell University)
Ola Svennson (EPFL)
Mikkel Thorup (University of Copenhagen)
Gregory Valiant (Stanford University)
Ryan Williams (MIT)

The first batch of invitations will be out soon together with the call for nominations, so do not be surprised if you get one.