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: http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f790.pdf

Michał Włodarczyk

If you always wanted to have one of our t-shirts, but never had a chance to get one, you can now get one for Christmas! Just drop me an email with the size and the color: blue or black (see photos below), and one of us will pass you one at SODA in San Diego. We have some (apx. 15) spare ones that we will be happy to giveaway. 

black

blue

I hope the next year HALG will be an exciting event that will be very interesting for many of you. So if you think that some paper is worth to be included into the program please email halg2019.nominations@gmail.com your nomination as soon as possible. It would be cool to get many nominations so that setting up the program will be easy for us.

Call for Nominations

 4th Highlights of Algorithms conference (HALG 2019)

Copenhagen, June 14-16, 2019

http://highlightsofalgorithms.org/

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

 To nominate, please email  halg2019.nominations@gmail.com  the
following information:

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

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.

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.

homepage: https://fc.isima.fr/~lupasto/

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.

On October 10, 2018, the National Science Centre Awards were presented for the sixth time. The prize, established in 2013 by the NCN Council, is awarded to scientists up to the age of 40 for significant achievements in the field of basic research conducted in Polish scientific institutions. Every year, the prize is given to representatives of three research areas: art, humanities and social sciences, life sciences, natural and technical sciences.

The NCN Award is also a platform for cooperation between business and science. Every year, companies involved in social and research activities are invited to cooperate in funding the awards. Such a formula enables direct support for the young leaders shaping the future of Polish science. This year's NCN Awards have been funded by: Adamed Group, Jastrzębska Spółka Węglowa and the KGHM Polska Miedź Foundation.

We are pleased to announce that this year winner in the group of natural and technical sciences is dr hab. Piotr Sankowski from University of Warsaw, Faculty of Mathematics, Informatics and Mechanics.

Congratulations!

We announce one-year postdoc positions (with possible extensions) at the Institute of Informatics, University of Warsaw, Poland. The positions are supported by the ERC Starting Grant CUTACOMBS: “Cuts and decompositions: algorithms and combinatorial properties” led by Marcin Pilipczuk and by the ERC Consolidator Grant TUgbOAT: “Towards Unification of Algorithmic Tools” led by Piotr Sankowski.

The CUTACOMBS’ focus is on structural graph theory and parameterized complexity. Example topics include:
* structure of separations in directed graphs, with applications to parameterized algorithms;
* approximability of the disjoint paths problem in various settings;
* structure of hereditary graph classes, such as graph excluding a fixed graph as induced subgraph, with algorithmic and graph-theoretical applications.
More information about the project can be found at http://cutacombs.mimuw.edu.pl/.

The TUgbOAT’s focus is to work on algorithms for core algorithmic problems.
Example topics include:
* faster algorithms for matchings and maximum flow problems;
* optimal online algorithms (when comparing to online opt);
* analyzing structure of real world networks and exploiting it algorithmically.

The theoretical computer science group in Warsaw is strong and growing. Apart from the algorithms group specializing in parameterized and approximation algorithms (Marek Cygan, Ł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,000PLN. For comparison, this translates to around twice the average salary in Poland. The position comes with a generous travel support and no teaching duties.

The application deadline is 10th September 2018. The starting date is flexible, but not earlier than 1st November 2018.

To apply, send a CV both to Marcin Pilipczuk (malcin@mimuw.edu.pl) and Piotr Sankowski (sank@mimuw.edu.pl). Please indicate your preference with regards to the project. Questions and informal inquiries are welcome.

This 'sweet and sour' news is already some time overdue. You might already know how a typical geographical distribution of ERC grants looks like. The next figure shows to which countries Consolidator grants went in 2017.

This distribution is usually typical for Poland, i.e., apx. 1 grant is given. This in general is rather 'sour' news. Still a 'sweet' information is that this was yet another grant in algorithms that went to our group in Warsaw. Hence, we currently have three ERC grants running:

1. Marcin Pilipczuk got ERC Starting Grant CUTACOMBS - Cuts and decompositions: algorithms and combinatorial properties,
2. Marek Cygan got ERC Starting Grant TOTAL - Technology transfer between modern algorithmic paradigms,
3. I, myself, got ERC Consolidator Grant TUGboAT - Towards Unification of Algorithmic Tools.

In other words, there are some interesting project happening right in Warsaw, and if you would like to visit us, just let us know.

Announcement of the ESA Test-of-Time Award 2017

European Symposium on Algorithms (ESA)
http://esa-symposium.org/

The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2017 award, papers from ESA'96 to ESA'98 were considered.

The committee nominates the following paper for the ESA ToTA 2017. The paper stands out as a classic in the algorithms field and continues to be cited as an exemplary study in its field.

From ESA 96-98:

James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook
A Functional Approach to External Graph Algorithms
Proceedings ESA'98, pp. 332-343
also in: Algorithmica 32 (2002) 437-458

Laudation:
The paper deals with the design of algorithms that operate on massive data sets in external memory. Building on the well-known I/O model of complexity by Aggarwal and Vitter, the authors introduce a novel design principle for external algorithms based purely on functional transformations of the data, which facilitates standard checkpointing and program optimization techniques. Illustrated on a variety of graph problems, their approach is proved to be elegant and versatile in the design of both deterministic and randomized external algorithms while the resulting I/O complexities remain competitive. Functional algorithms are also designed for semi-external problems, in which the
nodes fit in main memory but the connecting edges are abundant and only available in external memory. The paper is an excellent illustration of how general principles of functional program design and model-based complexity can remain in harmony in the field of external algorithms.

Award Committee:
Giuseppe F. Italiano (Rome),
Mike Paterson (Warwick),
Jan van Leeuwen (Utrecht)