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.

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

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.

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:

Nikhil Bansal

Artur Czumaj

Andreas Feldmann

Adi Rosén

Eva Rotenberg

Piotr Sankowski

Christian Sohler

]]>

**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 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 <sank@mimuw.edu.pl>.

Questions and informal inquiries are welcome.

]]>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.

]]>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.nominations@gmail.com 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

http://highlightsofalgorithms.

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.

------------------------------

PROGRAM

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:

2018.highlightsofalgorithms.or

------------------------------

REGISTRATION

Please register on our webpage

http://

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.

------------------------------

CONFERENCE VENUE

The conference will take place at the H.C. Ørsted Institute of the

University of Copenhagen.

The address is: Universitetsparken 5, DK-2100 Copenhagen.

------------------------------

INVITED SPEAKERS

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)

------------------------------

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, *a _{1}* ... and

To emphasize the significance of this question, let me cite David Eppstein: "A major bottleneck in proving NP-completeness for geometric problems is a mismatch between the real-number and Turing machine models of computation: one is good for geometric algorithms but bad for reductions, and the other vice versa. Specifically, it is not known on Turing machines how to quickly compare a sum of distances (square roots of integers) with an integer or other similar sums, so even (decision versions of) easy problems such as the minimum spanning tree are not known to be in NP."

"Is this problem computable at all?" - might the curious reader ask after realizing that the approach of iteratively increasing the precision until the first difference in digits will never terminate if both numbers happen to be equal. Luckily, Allan Borodin et al. and Johannes Blömer showed that polynomial time is enough to decide whether two such sums have the same value. Therefore, it is astonishing that the problem of deciding the sign of their difference, a question that seems only slightly harder, has been only recently spotted by Eric Allender et al on an island of the counting hierarchy CH (3rd level) located in the wide ocean of PSPACE. Thus, it is still far far away from the needle head of P, where Gregorio Malajovich conjectured it to live. Until this will be shown, Jeff Erickson proposes to study which problems are (non-boringly) Σ√-hard.

Oh, if we could only sufficiently bound the difference of the sums from below! Then we could bound from above the precision required to determine the correct sign of the difference: Just image that *B* is such a lower bound on the difference. Now, take a precision that allows us to compute an approximate difference being only *B/2* away from the real one. Then it is easy to verify that the following procedure determines the correct sign: Output the sign of the approximate difference if it is outside of *[-B/2,B/2]*, otherwise output *0*. What is the run time of this procedure? It is proportional to the precision, which corresponds to the length of *B*, that is, to *-log B*. Hence, if *-log B* is bounded from above by a polynomial in the length of the input, then we are in P! So, is there any reasonable lower bound for the worst case? That is, **what is the smallest positive difference between any two sums of k square roots of integers of size at most n?** Welcome to Problem 33 of The Open Problems Project! Let

In the dramatic opening of this post, I mentioned our paper, where the problem of Sum of Square Roots appeared. There, we design a PTAS for the Traveling Salesman problem (TSP) with hyperplane neighborhoods, that is, we look for a *(1+ε)*-approximation of a minimum-length tour that, instead of points, visits a given set of hyperplanes in ℝ^{d} with *d* being fixed. The basis of our algorithm is an integer grid of constant size (depending on *ε* and *d*). Our key observation is that there is a translation and scaling of the grid such that snapping an (adequately sparsified) optimum solution to the grid results in a *(1+ε*)-approximation. Using this insight, we let our algorithm enumerate all (reasonable) TSP tours lying in our integer grid. With a simple LP, we translate and scale each tour such that it visits all the hyperplanes of the input whilst minimizing its tour length (i.e., the scaling factor). At the end, we obtain a set of feasible TSP tours and output the shortest one. And here we were confronted with the Sum of Square Roots problem. Which of the tours is the shortest one? Was all our work devastated, all our blood, sweat and tears in vain? Just because the very last line of our algorithm had unknown complexity? Our solution was simple: We just skipped the issue and our paper got accepted. Why? Well, the issue wasn't one for the following three reasons:

- We could be lazy and assume the real RAM computational model with constant time for square root operations (as often done in computational geometry).
- We could be industrious and approximate the real tour lengths with a sufficiently small error since we look anyway for an approximation in overall.
- We could think and then realize that our candidate tours consist of only constant many vertices as our integer grid has constant size. Indeed, the best known lower bound on the difference
*r(n,k)*implies the following nice take-away which shall conclude this epilogue:

-------------------------

Proof sketches for the interested reader of the lower and upper bounds onFor all *m*, there is a 0-1 matrix *M* with k=*O*(*m* / log *m*) rows and *m* columns
such that for any *x*, *y* in {*a*,*b*}^{m}, x ≠ y implies *M x* ≠ *M y*.

For all *d*,*m*, there is a 0-1 matrix *M* with k=*O*(*m* *log* *d* / log *m*) rows and *m* columns
such that for any *x*, *y* in ℕ^{m} with ‖*y*‖_{1} ≤ *d* *m*, x ≠ y implies *M x* ≠ *M y*.