Keith Ball on Bourgain’s Legacy in Geometric Functional Analysis

The Bulletin of the AMS has just posted an article by Keith Ball on the legacy of Bourgain’s work on geometric functional analysis.

This beautifully written article talks about results and conjectures that are probably familiar to readers of in theory, but from the perspective of their mathematical motivations and of the bigger picture in which they fit.

Post-doc Opportunities in Milan

[call for applications] [application form]

I am recruiting two postdocs for two-year positions to work with me starting in Fall 2021 at Bocconi University. The positions have competitive salaries and are tax-free. If applicable, I will pay for relocation expenses, including the assistance of a relocation agency for help in finding a place to live and activate utilities, to complete immigration formalities, and to sign up for the national health care service.

Milan has been suffering as much or more than other European and American big cities for the effects of the Covid-19 pandemic. I have seen Milan in its normal condition for a few months from September 2019 to February 2020, and it is a beautiful cosmopolitan city, with an active cultural and social life, and with beautiful surroundings. Like San Francisco, it is smaller than one would expect it to be and very walkable (no hills!). Bocconi is situated in a semi-central area, about twenty minute walk from the Duomo.

I have received a large European grant that, besides paying for these postdoc positions, has a budget for senior visitors and for organizing two workshops over the duration of the grant. In particular, I was planning a workshop to be held last May in a villa on Lake Como. All such plans have been on hold, but Fall 2021 should be around the time that the global pandemic emergency ends, and I am planning for a lot of exciting scientific activity at Bocconi in the academic year 2021-22 and beyond.

I am looking for candidates with an established body of work on topics related to my research agenda, such as pseudorandomness and combinatorial constructions; spectral graph theory; worst-case and average-case analysis of semidefinite programming relaxation of combinatorial optimization problems.

Here are the call for applications and the application form.

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