A Couple of Announcements

In the second week of July, 2022, there will be a summer school on algorithmic fairness at IPAM, on the UCLA campus, with Cynthia Dwork and Guy Rothblum among the lecturers. Applications (see the above link) are due by March 11, 2022.

We will soon put up a call for nominations for the test of time award to be given at FOCS 2021 (which will take place in Boulder, Colorado, in early 2022). There are three award categories, recognizing, respectively, papers from FOCS 2011, FOCS 2001, and FOCS 1991. In each category, it is also possible to nominate older papers, up to four years before the target conference. For example, for the thirty-year category, it is possible to nominate papers from FOCS 1987, FOCS 1988, FOCS 1989, FOCS 1990, in addition to the target conference FOCS 1991.

Nominations should be sent by October 31, 2021 to focs.tot.2021@gmail.com with a subject line of “FOCS Test of Time Award”. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.

In the second week of November, 2021, the Simons Institute will host a workshop on using cryptographic assumptions to prove average-case hardness of problems in high-dimensional statistics. This is such a new topic that the goal of the workshop will be more to explore new directions than to review known results, and we (think that we have) already invited all the authors of recent published work of this type. If you have proved results of this type, and you have not been invited (perhaps because your results are still unpublished?) and you would like to participate in the workshop, there is still space in the schedule so feel free to contact me or one of the other organizers. For both speakers and attendees, physical participation is preferred, but remote participation will be possible.

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

Benny Chor

I just heard that Benny Chor died this morning. Chor did very important work on computational biology and distributed algorithms, but I (and probably many of my readers) know him primarily for his work on cryptography, for his work on randomness extraction and for introducing the notion of private information retrieval.

I only met him once, at the event for Oded Goldreich’s 60th birthday. On the occasion, he gave a talk on the Chor-Goldreich paper, which introduced the problem of randomness extraction from independent sources, and which introduced min-entropy as the right parameter by which to quantify the randomness content of random sources. He did so using the original slides used for the FOCS 1985 talk.

I took a picture during the talk, which I posted online, and later he sent me an email asking for the original. Sadly, this was the totality of our correspondence. I heard that besides being a brilliant and generous researchers, he was a very playful, likeable and nice person. My thoughts are with his family and his friends.

The Simons Institute Reopens

This coming Fall semester the Simons Institute for the Theory of Computing in Berkeley will have in-person activities, including the really interesting program on the complexity of statistical inference, within which I will co-organize a workshop on cryptography, average-case complexity, and the complexity of statistical problems.

As it had been the case before the pandemic, all Simons Institute events will be streamed and available remotely. This includes a new series of Public Lectures called “Breakthroughs” that starts next week with a talk by Virginia Williams on matrix multiplication.

Bocconi Hired Poorly Qualified Computer Scientist

Today I received an interesting email from our compliance office that is working on the accreditation of our PhD program in Statistics and Computer Science.

One of the requisites for accreditation is to have a certain number of affiliated faculty. To count as an affiliated faculty, however, one must pass certain minimal thresholds of research productivity, the same that are necessary to be promoted to Associate Professor, as quantified according to Italy’s well intentioned but questionably run initiative to conduct research evaluations using quantifiable parameters.

(For context, every Italian professor maintains a list of publications in a site run by the ministry. Although the site is linked to various bibliographic databases, one has to input each publication manually into a local site at one’s own university, then the ministry site fetches the data from the local site. The data in the ministry site is used for these research evaluations. At one point, a secretary and I spent long hours entering my publications from the past ten years, to apply for an Italian grant.)

Be that as it may, the compliance office noted that I did not qualify to be an affiliated faculty (or, for that matter, an Associate Professor) based on my 2016-2020 publication record. That would be seven papers in SoDA and two in FOCS: surely Italian Associate Professors are held to high standards! It turns out, however, that one of the criteria counts only journal publications.

Well, how about the paper in J. ACM and the two papers in SIAM J. on Computing published between 2016 and 2020? That would (barely) be enough, but one SICOMP paper has the same title of a SoDA paper (being, in fact, the same paper) and so the ministry site had rejected it. Luckily, the Bocconi administration was able to remove the SoDA paper from the ministry site, I added again the SICOMP version, and now I finally, if barely, qualify to be an Associate Professor and a PhD program affiliated faculty.

This sounds like the beginning of a long and unproductive relationship between me and the Italian system of research evaluation.

P.S. some colleagues at other Italian universities to whom I told this story argued that the Bocconi administration did not correctly apply the government rules, and that one should count conference proceedings indexed by Scopus; other colleagues said that indeed the government decree n. 589 of August 8, 2018, in article 2, comma 1, part a, only refers to journals. This of course only reinforces my impression that the whole set of evaluation criteria is a dumpster fire that is way too far gone.

Finally, a joy

In Rome we have an expression, mai una gioia (literally, “never (a moment of) joy”) that applies well to the present times. Yesterday, there was, finally, something to be joyous about: the announcement that two of my heroes, Laszlo Lovasz and Avi Wigderson, will share the 2021 Abel Prize, one of the highest honors of mathematics.

The reader can find a very good article about them on Quanta Magazine.

Instead of talking about their greatest accomplishment, here I would like to recall two beautiful and somewhat related results, that admit a short treatment.

Continue reading

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.