- 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 (use Warsaw local time) and we will do our best to find a working slot. If there are a lot of submissions, we may assign less time to each talk and if this does not help, we may assign slots on the first–come first–serve basis.
- If you have not registered but you are coming in person, please do this ASAP. If you are planning on joining remotely, this will also help us with keeping you updated.
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:
# 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
register as soon as possible at
https://ideas-ncbr.pl/en/wola/registration/. Even if you are not
planning to give a talk, registering helps the local organizers with
estimating the number of attendees, which is useful for events such as...
# A night tour of Warsaw on a retro bus
See the attached picture for what such a bus looks like! I'm told by the
local organizers that this will include a tasting of Polish specialties.
This event is scheduled for Saturday night.
# Traveling from STOC in Rome
The workshop is starting at 1:30pm on Saturday to allow for more options
for traveling from STOC. There are direct flights with Wizz Air on both
Friday night and Saturday morning. You can also fly with KLM (via AMS)
or Air France (via CDG) on Saturday morning if you prefer a more
traditional air carrier.
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 held on the 1st of October 2020.
October 1, 2020
Vera Traub, University of Bonn
Title: An improved approximation algorithm for ATSP
Abstract: In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it.
Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio.
Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.
This is joint work with Jens Vygen.
Other upcoming talks include:
October 15, 2020
Thatchaphol Saranurak, Toyota Technological Institute at Chicago
Title: An almost-linear time deterministic algorithm for expander decomposition
October 29, 2020
Nathan Klein, University of Bonn
Title: A (Slightly) Improved Approximation Algorithm for Metric TSP
For more details please contact the Organization Committee:
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/watch?v=xoodhmjJ9Xs .
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. The application deadline is 15th March 2020. The default length of the contract is one year. The starting date is flexible.
To apply, send a CV to Piotr Sankowski <email@example.com>.
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:
- 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 TUgbOAT.
Watch a video and find out more about benefits of working at MIM UW.
5th Highlights of Algorithms conference (HALG 2020)
ETH Zurich, June 3-5, 2020
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 firstname.lastname@example.org the following information:
- Basic details: speaker name + topic (for survey talk) or paper’s title, authors, conference/arxiv + preferable speaker (for paper talk).
- 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 20, 2020 (for full consideration).
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.
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)
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)
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