Silver linings

To put it mildly, 2020 is not shaping up to be a great year, so it is worthwhile to emphasize the good news, wherever we may find them.

Karlin, Klein, and Oveis Gharan have just posted a paper in which, at long last, they improve over the 1.5 approximation ratio for metric TSP which was achieved, in 1974, by Christofides. For a long time, it was suspected that the Held-Karp relaxation of metric TSP had an approximation ratio better than 1.5, but there was no viable approach to prove such a result. In 2011, two different approaches were developed to improve 1.5 in the case of shortest-path metrics on unweighted graphs: one by Oveis Gharan, Saberi and Singh and one by Momke and Svensson. The algorithm of Karlin, Klein and Oveis Gharan (which does not establish that the Held-Karp relaxation has an integrality gap better than 1.5) takes as a starting point ideas from the work of Oveis Gharan, Saberi and Singh.

Continue reading

“Visioning” workshop call for participation

In 2008, the Committee for the Advancement of Theoretical Computer Science convened a workshop to brainstorm directions and talking points for TCS
program managers at funding agencies to advocate for theory funding. The event was quite productive and successful.

A second such workshop is going to be held, online, in the third week of July. Applications to participate are due on June 15, a week from today. Organizers expect that participants will have to devote about four hours of their time to the workshop, and those who volunteer to be team leads will have a time commitment of about ten hours.

More information at this link

Spectral Sparsification of Hypergraphs

In this post we will construct a “spectral sparsifier” of a given hypergraph in a way that is similar to how Spielman and Srivastava construct spectral graph sparsifiers. We will assign a probability {p_e} to each hyperedge, we will sample each hyperedge {e} with probability {p_e}, and we will weigh it by {1/p_e} if selected. We will then bound the “spectral error” of this construction in terms of the supremum of a Gaussian process using Talagrand’s comparison inequality and finally bound the supremum of the Gaussian process (which will involve matrices) using matrix Chernoff bounds. This is joint work with Nikhil Bansal and Ola Svensson.

Continue reading

Spielman-Srivastava Sparsification à la Talagrand

This is the second in a series of posts explaining a result on hypergraph sparsification that uses Talagrand’s work on Gaussian processes.

In the previous post we talked about Gaussian and sub-Gaussian processes and generic chaining.

In this post we talk about the Spielman-Srivastava probabilistic construction of graph sparsifiers. Their analysis requires a bound on the largest eigenvalue of a certain random matrix, that can be derived from matrix Chernoff bounds.

We will then make our life harder and we will also derive an analysis of the Spielman-Srivastava construction by casting the largest eigenvalue of that random matrix as the sup of a sub-Gaussian process, and then we will apply the machinery from the previous post.

This will be more complicated than it needs to be, but the payoff will be that, as will be shown in the next post, this more complicated proof will also apply, with some changes, to the setting of hypergraphs.

Continue reading

Talagrand’s Generic Chaining

Welcome to phase two of in theory, in which we again talk about math. I spent last Fall teaching two courses and getting settled, I mostly traveled in January and February, and I have spent the last two months on my sofa catching up on TV series. Hence I will reach back to last Spring, when I learned about Talagrand’s machinery of generic chaining and majorizing measures from Nikhil Bansal, in the context of our work with Ola Svensson on graph and hypergraph sparsification. Here I would like to record what I understood about the machinery, and in a follow-up post I plan to explain the application to hypergraph sparsification.

Continue reading

The peak, the plateau, and the phase two

What has been happening in Italy in the last few days, and what can other Western countries expect in the next week or two?

The national discourse has been obsessed with “The Peak,” that is, the time when things reach their worst point, and start improving after that. For the last several days, all indicators, such as new cases, deaths, and ICU occupancy, have been improving. Apparently, then, “The Peak” is behind us. Virologists have been cautious to say that “peak” is the wrong mountain metaphor to use, and that we have rather reached a “plateau” in which things will change very slowly for a while.

Below is the number of confirmed covid-19 deaths in Italy updated with today’s data, showing that we reached the plateau a couple of weeks ago, meaning that the number of new cases started to plateau about a month ago, when the lockdown started.

italy-deaths

The data from New York City continues to track the data from Lombardy, so NYC should be just a few days away from its own plateau, if the match continues.

lombardy-nyc

lombardy-nyc-daily

Given all this, people have been wondering when and how we will get out of the lockdown, and reach what everybody has been calling the “Phase Two” of this emergency.

Continue reading

On virus containment as dieting

The Protezione Civile, the Italian equivalent of FEMA, holds a daily press conference to announce coronavirus data from the previous 24 hours. Today they had relatively good news, of which we hope to hear more soon. The Protezione Civile puts a lot of data online every day, on github, which allows any interested party to monitor the situation and will allow people in other countries to see the effect of our various restrictive measures over time.

The graph below, which is courtesy of Carlo Lucibello, shows the number of deaths in Italy on a logarithmic scale, compared with data from China from 36 days before.
90441248_574660963135651_9199184881282711552_n
(Image credit: Carlo Lucibello)

At the start, Italian deaths rose like in China, at the same exponential rate. About twenty days after the lockdown of Wuhan, the Chinese data started deviating from the exponential rate and leveled off. In Italy, about ten days ago, there was a slowdown, which followed the institution of the “yellow zone” by about 15 days. The “yellow zone” measures closed schools, universities, museums, cinemas, and clubs, and restricted hours of bars and coffee shops, in Lombardy. Apparently, although these measures made a difference, they still allowed the spread of the virus to continue at an exponential rate.

On March 8, Lombardy was put on a stricter lockdown, with travel restrictions, and on March 10 the lockdown was extended to the rest of the country. So we may hope to see a stronger slowdown and maybe a leveling-off two or three weeks after these measures, that is, any day now. It may seem premature to ask this question, but what happens next?

Today the Italian government announced additional measures to facilitate “social distancing,” halting all “non-essential” manufacturing and other work activities, forbidding people from leaving the house to walk or jog (even alone), and further restricting the cases in which it is allowed to travel between different cities.

These measures, which apply nationwide, are meant to be in place for two weeks. They will be economically devastating (even more so than the already devastating nationwide lockdown of March 10), and they will be difficult to keep in place for longer than the expected two weeks.

When a nationwide “lockdown” was first instituted, the prime minister announced it by saying “let’s be distant today in order to more warmly hug each other tomorrow”. In general, the spirit of these measures has been to suffer for a short time and then return to normal.

This feels like the national mood in general, and the government took today’s further restrictive measures somewhat reluctantly, because there was strong popular support for them.

Here I am worried that we are approaching this crisis the way many people attempt to lose weight: by going on a starvation diet, then losing some weight, then celebrating and finally gaining back more weight than they lost.

The point being that I worry about what will happen once the worst is over and these restrictive measures will be lifted. Until there is a vaccine or a cure, we will not be able to really go back to normal, and we will have to make some sustainable “lifestyle changes” to “maintain” what we got, just like people who maintain weight loss for a long time do so by making sustainable changes for the long term.

Concretely, we will need a very efficient system to monitor new cases and trace contacts, perhaps similar to Taiwan’s, and to follow the kind of stricter hygiene precautions in public places that have been common in East Asia since SARS. Let’s hope that we will have to worry about such problems soon.