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.

2018 NCN prizes awarded!

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.



Postdoc positions in Warsaw (algorithms)

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.

Sweet and Sour News

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.

ESA Test-of-Time Award 2017

Announcement of the ESA Test-of-Time Award 2017

European Symposium on Algorithms (ESA)

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

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)


Call for Nominations for Invited Talks 3rd Highlights of Algorithms conference (HALG 2018)

The call for nominations for invited talks for HALG 2018 is open till 12th of December! See below.

Call for Nominations for Invited Talks.
3rd Highlights of Algorithms conference (HALG 2018)
Amsterdam, June 4-6, 2018

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

To nominate, please email  halg2018.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. Pay attention to potentially non-obvious information, e.g., the topic might seem out of scope, or the material seems inadequate for one talk.

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

Nominations deadline: December 12, 2017 (for full consideration).

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

Best regards,
Robert Krauthgamer,
HALG 2018 PC chair.

Some pictures from ICALP

On 10-13 July we hosted ICALP in Warsaw. It was fun! See a few random pictures below.

Invitation to Award Ceremony of the ESA Test-of-Time Award 2016

On behalf of the Steering Committee of ESA and the Program Committee of ESA 2017,
I would like to invite you to attend the ESA conference and the ESA Test-of-Time 2016 Award Ceremony. The ceremony will take place on the afternoon of 5th of September during ESA 2017 in Vienna and it will include the presentation by the awardees of the recognized paper.
Announcement of the ESA Test-of-Time Award 2016

European Symposium on Algorithms (ESA)

The ESA Test-of-Time Award (ESA ToTA) recognizes excellent 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. In this second year in which the award is given, papers from ESA'95 to ESA'97 were considered.

The committee nominates the following paper for the ESA ToTA 2016. The paper stands out as a classic in the algorithms field and by its excellent citation
record still relevant today.

From ESA 95-97:

Boris V. Cherkassky, Andrew V. Goldberg
Negative-cycle detection algorithms
Proceedings ESA'96, also in: Mathematical Programming 85:2 (1999) 277-311

The paper by Cherkassky and Goldberg deals with the problem of finding a
negative-length cycle in a network or proving that there is none. Algorithms
for this are a combination of a shortest-path algorithm and a negative-cycle
detection strategy. The authors analyse known algorithms and some new ones
and determine the best combinations. Novel instance generators are used in
this study. The paper is a model experimental paper in algorithms.

ESA ToTA 2016 Award Committee:
Kurt Mehlhorn (Saarbrucken)
Mike Paterson (Warwick)
Jan van Leeuwen (Utrecht)


We in Warsaw, recently stumbled upon http://csrankings.org/ which ranks CS departments world-wide according to publication counts in mayor conferences. A cool aspect of this ranking is that one can set the year range for the counted publications. We rather only very recently, i.e., during the last 5-10, started doing well, so this parameter allows to track this change. As we are working mostly in theory let us restrict the ranking to theory only, i.e, Algorithms & complexity; Cryptography; Logic and verification. If you set the range to start in 2000 - to contain the last 15 years, then we are placed on position 10 world-wide. Quite cool already. Setting the starting point to 2005 bumps us to the 6th position. The most interesting part happens when you set the starting point to 2010, i.e., last 5 years, as you get the following table:

Rank Institution Average Count Faculty
1 University of Warsaw 8.4 24
2 Massachusetts Institute of Technology 8.2 20
3 University of Texas - Austin 7.3 8
4 Stanford University 7.1 12
5 Cornell University 6.9 14
6 Northeastern University 6.1 10
7 New York University 5.9 10
7 Carnegie Mellon University 5.9 14
9 University of Illinois at Urbana-Champaign 5.7 14
9 University of California - San Diego 5.7 10

Quite surprising... as all the ranking are usually. However, there might be some reasons for this. First of all, we cover all three areas that are counted in theory. For example, logic is visibly stronger in Warsaw than in other places included in top 10. Second, we indeed started doing quite well, e.g., we got 6 ERC grants so far. I do not really believe in rankings, but at least it is some indication that Warsaw is not such a bad place to be - see the cat meme.

Bratislava Declaration of Young Researchers

The Bratislava Declaration of Young Researchers is something I was involved in recently. Its preparation was inspired by Slovak Presidency of the EU and it was presented on today's informal Council of Ministers responsible for competitiveness (Research). I hope this will have some follow up, as current trend in funding research in EU is in my opinion (and not only my as this declaration shows) going in the wrong direction.