Workshop in Milan Next Week

As previously announced, next week Alon Rosen and I are organizing a workshop at Bocconi, which will actually be the union of two workshops, one on Recent Advances in Cryptography and one on Spectral and Convex Optimization Techniques in Graph Algorithms. Here is the program. In short:

  • where: Bocconi University’s Roentgen Building (via Roentgen 1, Milano), Room AS01
  • when: June 15-18
  • what: talks on cryptography and graph algorithms, including two hours devoted to Max Flow in nearly-linear time
  • how: register for free

Postdoc Positions

The call is out for two postdoctoral positions at Bocconi to work in my group (see below for how to apply). If you are interested and you have any questions, feel free to email me (L.Trevisan at Unibocconi dot it)

The negotiable start date is September 1st, 2022. Each position is for one year, renewable for a second. The positions offer an internationally competitive salary (up to 65,000 Euro per year, tax-free, plus relocation assistance and travel allowance), in a wonderful location that, at long last, is back to more or less normal life. The application deadline is December 17, 2021.

Among the topics that I am interested in are spectral graph theory, average-case complexity, “applications” of semidefinite programming, random processes on networks, approximation algorithms, pseudorandomness and combinatorial constructions.

Bocconi Computer Science is building up a theory group: besides me, we have Alon Rosen, Marek Elias, a tenured person that will join next Fall, and more hires are on the horizon. Now that traveling is ok again, and considering that Alon and I both have ERC grants, we should expect a big stream of theory visitors coming and going through Bocconi from week-long visits to semester or year long sabbaticals.

To apply, go to and look for the position advertised as “BIDSA Informatics”, which looks like this:

and click on “apply online”. Currently it is the second position from the top in the list

The Third Annual “Why am I in Italy and you are not?” post

I moved back to Italy exactly two years ago. I was looking for some change and for new challenges and, man, talk about being careful what you wish for!

Last year was characterized by a sudden acceleration of Bocconi’s plans to develop a computer science group. From planning for a slow growth of a couple of people a year until, in 5-7 years, we could have the basis to create a new department, it was decided that a new computer science department would start operating next year — perhaps as soon as February 2022, but definitely, or at least to the extent that one can make definite plans in these crazy times, by September 2022.

Consequently, we went on a hiring spree that was surprisingly successful. Five computer scientists and four statistical physicists have accepted our offers and are coming between now and next summer. In computer science, Andrea Celli (who won the NeurIPS best paper award last year) and Marek Elias started today. Andrea, who is coming from Facebook London, works in algorithmic game theory, and Marek, who is coming TU Eindhoven, works in optimization. Within the next couple of weeks, or as soon as his visa issues are sorted out, Alon Rosen will join us from IDC Herzliya as a full professor. Readers of in theory may know Alon from his work on lattice-based cryptography, or his work on zero-knowledge, or perhaps his work on the cryptographic hardness of finding Nash equilibria. Two other computer science tenured faculty members are going to come, respectively, in February and September 2022, but I am not sure if their moves are public yet.

Meanwhile, I have been under-spending my ERC grant, but perhaps this is going to change and some of my readers will help me out.

If you are interested in coming to Milan for a post-doc, do get in touch with me. A call will be out in a month or so.

After twenty years in Northern California, I am still readjusting to seasonal weather. September is among Milan’s best months: the oppressive heat of the summer gives way to comfortable days and cool nights, but the days are still bright and sunny. Currently, there is no quarantine requirement or other travel restrictions for fully vaccinated international travellers. If you want to visit, this might be your best chance until Spring Break (last year we had a semi-lockdown from late October until after New Year, which might very well happen again; January and February are not Milan’s best months; March features spectacular cherry blossoms, and it is again an ok time to visit).

This year, for Lent, we realized it has been Lent all along

Yesterday was Ash Wednesday, the beginning of Lent, the 40-day period that precedes Easter and that is observed by Catholics and other Christians as a period of reflection. It is, often, a period in which the faithful choose to give something up as a penance, such as giving up eating meat.

The period that immediately precedes Lent is known as Carnival, and, perhaps incongruously, it is a time for having fun, playing pranks, and eating special sweets, often deep-fried ones. Traditionally kids, and also grownups, dress up in costumes and attend costume parties. The idea being, let’s have fun and eat now, because soon we are “entirely voluntarily” going to fast and to reflect on sin and death, and stuff like that. The day before Ash Wednesday, indeed, is called “Fat Tuesday”.

In Milan, however, the tradition is to power through Ash Wednesday and to continue the Carnival festivities until the following Sunday. There are a number of legends that explain this unique tradition, that is apparently ancient. One such legend is that a plague epidemic had been ravaging Milan in the IV century around the time that should have been Carnival, and life was beginning to go back to normal right around Ash Wednesday. So people rebelled against Lent, and were like, haven’t we suffered enough, what more penance do we need, and celebrated Carnival later.

It has now been nearly a year since the first lockdown, and we still cannot travel between regions (for example, we cannot travel from Milan to Bologna, or to Venice), cannot eat dinner in a restaurant, cannot go see a movie, a play or a sporting event, cannot ski, and so on.

My proposal is that when (if?) we go back to a normal life, we shorten Lent to three days (start with “Ash Thursday” the day before Good Friday), and that we make Carnival start on Easter Monday and last for 361 days. Not because we have had it worse than a IV century plague epidemic: indeed, even in the best of times, IV century people in Milan did not usually eat in restaurants, travel to Venice, see movies, or ski. We, however, are spoiled XXI century people, we are not used to inconveniences, and when (if?) this is over we will need a lot of self-care, especially the eating-deep-fried-sweets-and-partying kind of self-care.

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.

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.

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.