An Unusual Year, in Pictures

Some memories from 2020.

When the year began I was in Hong Kong.

I got to see the tail end of the latest round of pro-democracy and pro-freedom protests, which had started several months earlier in response to a proposed new extradition law. The proposal ignited protests because many people saw the point of the law as allowing the PRC to bring trumped-up charges against pro-democracy Hong Kongers, and then request their extradition, thus avoiding the extrajudicial kidnappings that had been the primary way of bringing dissidents to the mainland. (In June 2020, the PRC sidestepped the issue by throwing away whatever was left of the handover agreements, and passing its own anti-sedition law and imposing it on Hong Kong, making it possible to jail dissenters directly in Hong Kong.)

On January 1, I went to one of the big demonstrations, in Victoria Park, and saw Joshua Wong, the pro-democracy leader who is currently serving a jail term on the basis of the June 2020 laws.

In the video below. the audio is not clear, but people are chanting “five demands, not one less” and “fight for freedom, stand with Hong Kong”. The five demands were to drop the extradition law, institute universal suffrage in elections, and the other three demands related to investigating and punishing police abuses against protesters.

In those days, I was reading English-language Hong-Kong press to keep up to date on protests that could cause the subway to shut down, and I noticed some reporting on a cluster of pneumonia cases in Wuhan. Since the time of SARS, Hong Kongers have been quite paranoid about new respiratory diseases coming from the mainland, but the reports were that no human-to-human transmission had been confirmed. (Speaking of Hong Kong press, the publisher of the Apple Daily newspaper is now in jail on the basis of the June 2020 legislation, because of his pro-democracy position.)

The reason I remember this is that on January 2 I came down with a fever and a cough. On my flight back, several days later, I coughed for the whole flight, without a face mask. Those being more innocent times, nobody seemed to mind.

Between January 31 and February 3 I was in London for an event organized by Bocconi. The evening of January 31 happened to be the moment Brexit went into effect, after the negotiations had blown past several deadlines, and after being pushed back several times. As it happened, negotiations continued for the rest of the year, and were not resolved until a few days ago. Although Brexit was on everyone’s mind, there was concern about the novel Coronavirus that had been isolated in Wuhan, which had proved to transmit person-to-person, and that had led to a health emergency and a severe lockdown of the city of Wuhan.

(Photo taken in London, Feb 2, 2020)

Back in Milan, I was looking forward to a Spring semester in which I was not teaching, and to the plans to take several trips and to host a number of academic guests.

Meanwhile, the Italian government had established a protocol according to which Covid19 testing was restricted to people who had had contact with a person known to suffer from Covid19 or who had recently traveled to China. Since nobody in Italy was known to suffer from Covid19, there was a bit of a chicken-and-egg problem going on, even as the virus (as became clear in retrospect) was spreading widely in Northern Italy.

Eventually, a person with Covid19 symptoms reported to have had dinner with a friend who had been to China. That person was tested, and, while he was already in intensive care, he became the first confirmed case of local transmission, on February 21. It then became clear that the friend who had been to China had never been infected, and that there must have already been a number of local infections. This was in the middle of Milan Fashion Week, which had already been scaled down due to concern about international travel. It was going to be the last major public event to take place in Milan for a while.

The following week, the Italian government settled on its response strategy: take some measures, back down after concern for the economic consequences, then double down when the situation gets worse. On March 1 I traveled to Rome in a mostly empty train. While a measure of panic was starting to gather in Milan (where it had become impossible to buy face masks and there were some shortages of other supplies in supermarkets), Romans were still mostly in denial. Tourism, however, had died down completely, and the city center was empty as I had never seen it.

(Piazza di Spagna and Via dei Condotti seen from Trinità dei Monti on March 1, 2020. I had never seen Piazza di Spagna empty of people ever before).

The following week (see above on government strategy), the initial measures that had closed bars and restaurants in Milan were relaxed, and bars could open but could only do table service.

(A bar in the Navigli district of Milan on March 7, 2020. The counter area was roped-off, and they only provided table service.)

On the night of March 7, as I was having my sit-down drink with a friend, I started receiving text messages saying that the prime minister was about to speak on TV and that there were rumors that the government would lock down Northern Italy. As people literally ran to the train station to catch the last train out of Milan, the press conference was delayed until late at night, and he did announce a lockdown of Northern Italy, which would be extended to the whole country a few days later.

After that, time is a blur. I read a very interesting article on this topic (but I cannot find it again now), whose point was that when nothing interesting happens, time seems to stretch, and the days feel long and empty. But because nothing interesting happens, we do not form new long-term memory, so later it feels like that time went by very quickly. This warped perception is part of the sense of dislocation that some of us felt during the lockdown.

I looked at my pictures from those months for a clue as to what happened, and it’s basically pictures of things that I cooked and of the unfortunate results of cutting my hair with a beard trimmer. The lockdown was extremely strict until May, banning even taking a walk outside alone. In May we could again walk outside, but the city felt eery and empty.

(The Italian stock exchange in Piazza Affari, Milan, on May 10, 2020. Maurizio Cattelan‘s iconic sculpture is visible in the foreground.)

During the summer, Covid19 cases, and especially Covid19 deaths, dropped considerably, and most business were allowed to reopen. Movie theaters, concert halls, stadiums, conference centers, and other venues where large numbers of people congregate remained closed. Dance clubs, however, reopened, and schools reopened in September.

By mid-October, numbers were about half the thresholds that were considered alarming. There were more than a thousand Covid19 patients in intensive care, for example, and two thousand was considered the threshold at which there would be a shortage of ICU beds for other patients. Furthermore, the numbers were doubling roughly every ten days, and any new measures would take about two weeks to have any effect. I wasn’t teaching until the second week of November. I did the math and I moved to Rome.

By the end of October, Bocconi had moved almost all teaching online, and the government had instituted new measures, this time on a regional basis. Milan was in a “red” region, and got a lockdown almost as bad as the one in the Spring. Rome was in a “yellow” region and there was a bit more freedom: retail was open, and indoor dining was possible for lunch.

I went back to Milan just before Christmas, when there have been further restrictions to avoid the large gatherings that are common during the Christmas holidays. They might have actually overshot a bit with the restrictions.

(This is Piazza Duomo in Milan, in the early evening of December 26, 2020. The emptiness and the tinny Christmas music made it feel like the setting of a horror movie.)

The day after I shot the above video, the European vaccine campaign got started. In July 2020, I was supposed to travel to Taipei. While all the other international events I had planned to attend in 2020 were canceled, the even in Taipei was moved to July 2021. I am looking ahead at what surely be another difficult Winter and Spring, but I am holding out hope to be in Taiwan in July and in Berkeley in November.

Best wishes to all readers, and may 2021 be a much less interesting year than the current one.

Kim Ki-duk

(Last call for the postdoc positions I advertised earlier. Application deadline is tomorrow morning Italian time, tonight American time.)

Last weekend I was saddened to hear of the death of Korean filmmaker Kim Ki-duk. Kim was in Latvia, preparing to shoot a movie there. He disappeared about a week ago, and it then transpired that he had been hospitalized with Covid symptoms, and died last Friday from Covid complications.

In the early 2000s, living in the San Francisco Bay Area offered me several opportunities to discover cinema that was new to me. There were the several film festivals held each year in San Francisco, the wonderful retrospectives at the Castro Theater. There was also Netflix, that at the time operated by renting DVDs by mail (I am feeling like grandpa Simpson telling stories here) and whose catalog was basically every movie ever released in the US. I discovered the work of Hirokazu Kore-eda and Wong Kar-Wai, whose movies are now among my favorites, and I watched some challenging but rewarding movies by the likes of Tsai Ming-Lian and Hou Hsiao-Hsien. So, when it came out, I watched “3-iron” by Kim Ki-duk, an amazing movie on the theme of the poor being invisible to the rich, but taken to extreme and fantastical places.

I was reminded of that time during our first lockdown last Spring. After having watched a lot of TV series, I felt like I had to do something a bit more soul-nourishing before the lockdown ended. So I resolved to watch Tarkovsky’s “Solaris” and “Stalker”, which I had never seen. Compared with movies I had watched 15+ years ago like those of Tsai Ming-Lian and Hou Hsiao-Hsien, or like “3-iron”, “Solaris” was like a Michael Bay movie full of explosions and car chases, but I still had a really hard time getting into it. I ended up watching it over five or six sittings, across a couple of weeks (the lockdown actually ended before I was done watching it). I still haven’t seen “Stalker”. I suppose that twelve years of smartphone usage accounts for the difference in attention span.

Bocconi is Looking for Assistant Professors in Computer Science

[application page] [call for applications]

Bocconi University is looking for two Tenure-Track Assistant Professors in Computer Science, for positions starting in Fall 2021. This is in the context of a build-up toward a new department focused on Computer Science, which is part of the University’s strategic plan, and which is expected to be launched by Fall 2022.

Bocconi is Italy’s premiere private University, located in Milan. It is well known for its excellence in Economics and Management, and a few years ago it has begun a push into the hard sciences and engineering. Currently it offers a Bachelor on Economics, Management and Computer Science, a Bachelor on Mathematical and Computing Sciences for Artificial Intelligence, and a Master’s in Data Science and Analytics. There is a PhD program in Statistics and Computer Science. Additional programs related to computing are being planned.

The University negotiates salaries on an individual basis, and is able to put together very competitive offer packages. Scholars moving to Milan from outside Italy gain, in addition, a 6+ year tax break (90% of the salary is exempt from income tax). The University provides relocation benefits and employs full time staff to assist non-Italian-speaking faculty. Students are admitted on the basis of a competitive admission exam. A large fraction of them are foreigners, and the general academic level is fairly high.

A special note for Italians on how the position relates to positions in public Universities (in Italian because this is only a local concern): la posizione di “assistant professor” è simile a quella di RTDA, ma è un contratto di diritto privato. Dopo una valutazione intermedia, si passa ad una posizione simile a RTDB, ma sempre con un contratto distinto di diritto privato, e dopo una tenure review si viene promossi ad associati. I ruoli di associati ed ordinari sono inquadrati nel sistema nazionale e parificati (a parte la possibilità di una integrazione salariale) ai corrispettivi ruoli nell’università pubblica. Anche se non sono io la persona più qualificata per discutere questi aspetti, rispondo volentieri a qualunque domanda.

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