This year, for Lent, we gave up being renters in Milan

The First XL Computer Scientist

Some time ago, I received a message to the effect that I was being considered for membership in the “Academy of the XL”, to which my reaction was, hey, we have all gone out of shape during the pandemic, and body-shaming is never… then it was explained to me that, in this context, “XL” means “forty” and that the Academy of the Forty is Italy’s National Academy of Science.

Italy has a wonderfully named, and well-known within the country, National Academy of Arts and Science, the Accademia dei Lincei, which means something like academy of the “eagle-eyed” (literally, lynx-eyed), that is, people that can see far. The Accademia dei XL is much less well known, although it has a distinguished 240-year history, during which people like Guglielmo Marconi and Enrico Fermi were members. More recently, the much beloved Rita Levi-Montalcini, Holocaust survivor, Nobel Laureate, and Senator-for-life, was a member. Current members include Nobel Laureates Carlo Rubbia and Giorgio Parisi. Noted algebraist Corrado De Concini is the current president.

Be that as it may, the academicians did vote to make me a member, their first computer scientist ever. Next week, at the inauguration of their 240th academic year, I will speak to the other members about randomness and pseudorandomness in computation.

Renato Capocelli (1940-1992)

Thirty years ago, I was in the middle of the second semester of my third year of undergrad, and one of the courses that I was enrolled in was on information theory. I was majoring in computer science, a major that had just been established at Sapienza University when I signed up for it in 1989, organized by a computer science department that had also just been established in 1989. A computer science department was established in 1991.

The new Sapienza computer science department was founded mostly by faculty from the Sapienza mathematics department, plus a number of people that came from other places to help start it. Among the latter, Renato Capocelli had moved to Rome from the University of Salerno, where he had been department chair of computer science.

Capocelli worked on combinatorics and information theory. In the early 90s, he had also become interested in the then-new area of zero-knowledge proofs.

Capocelli taught the information-theory course that I was attending, and it was a very different experience from the classes I had attended up to that point. To get the new major started, several professors were teaching classes outside their area, sticking close to their notes. Those teaching mathematical classes, were experts but were not deviating from the definition-theorem-proof script. Capocelli had an infectious passion for his subject, took his time to make us gain an intuitive understanding of the concepts of information theory, was full of examples and anecdotes, and always emphasized the high-level idea of the proofs.

I subsequently met several other charismatic and inspiring computer scientists and mathematicians, though Capocelli had a very different personality from most of them. He was like an earlier generation of Southern Italian intellectuals, who could be passionate about their subject in a peculiarly non-nerdy way, loving it the way one may love food, people, nature, or a full life in general.

On April 8, 1992, Renato Capocelli died suddenly and unexpectedly, though his memory lives on in the many people he inspired. The Computer Science department of the University of Salerno was named after him for a period of time.

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.

Time Flies When the World is Falling Apart

It has been exactly one year since I moved to Italy.

Coming here a year ago, I expected that I would face some challenges and that there would be major life changes. Obviously, I did not know the half of it.

What is next?

Greetings from the future! The progression of covid-19 in Italy is running about eight days ahead of France and Spain and about 16 days ahead of the United States. Here in Lombardy, which is about ten days ahead of NYC, we have been “sheltering at home” for 13 days already.

How is social distancing working out for me? I thought that I was well prepared for it, but it is still not easy. I have started to talk to the furniture, and apparently this is perfectly normal, at least as long as the furniture does not talk back.

As I have been telling my dining table, it has been very dismaying to read news from the US, where there seemed to be a very dangerous complacency. I am relieved to see that this is changing, especially at the state level, which makes me much more hopeful.

I have also found media coverage to be disappointing. Apparently, many highly educated people, including people whose job involves understanding policy issues, have no idea how numbers work (source). This is a problem because a lot of issues concerning this epidemic have to do with numbers, which can be misleading if they are not reported in context.

For example, before the time when Trump decided that he had retroactively been concerned about a pandemic since January, conservative media emphasized the estimate of a 2% mortality rate, in a way that made it sound, well, 98% of people survive, and 98% is approximately 100%, so what is the big deal. For context, the Space Shuttle only exploded 1.5% of the times, and this was deemed too dangerous for astronauts. This is the kind of intuitive reference that I would like to see more of.

Even now, there is a valid debate on whether measures that will cost the economy trillions of dollars are justified. After all, it would be absurd to spend trillions of dollars to save, say, 10,000 lives, it would be questionable to do so to save 100,000 lives, and it would be undoubtedly right to do so to save millions of lives and a collapse of the health care system (especially considering that a collapse of the health care system might create its own financial panic that would also cost trillions of dollars).

So which one is it? Would doing nothing cost 10,000 American lives? A million? How long will people have to “shelter at home”? And what is next? I can recommend two well-researched articles: this on plausible scenarios and this on what’s next.

Kristof’s article cites an essay by Stanford professor John Ioannidis who notes that it is within the realm of possibilities, given the available data, that the true mortality rate could be as low as 0.05%, that is, wait for it, lower than the mortality rate of the flu. Accordingly, in a plausible scenario, “If we had not known about a new virus out there, and had not checked individuals with PCR tests, the number of total deaths due to “influenza-like illness” would not seem unusual this year.”

Ioannidis’ essay was written without reference to data from Italy, which was probably not available in peer-reviewed form at the time of writing.

I would not want professor Ioannidis to tell me how to design graph algorithms, and I don’t mean to argue for the plausibility of the above scenario, but let me complement it with some data from Italy.

Lombardy is Italy’s richest and most developed region, and the second richest (in absolute and PPP GDP) administrative region in Europe after the Ile de France (source). It has a rather good health care system. In 2018, on average, 273 people died per day in Lombardy of all causes (source). Yesterday, 381 people died in Lombardy with coronavirus (source). This is spread out over a region with more than 10 million residents.

Some areas are harder-hit hotspots. Three days ago, a Bergamo newspaper reported that 330 people had died in the previous week of all causes in the city. In the same week of March in 2019, 23 people had died. That’s a 14x increase of mortality of all causes. Edited to add (3/22/2020): the mayor of Bergamo told Reuters that 164 people died in Bergamo of all causes in the first two weeks of March 2020, versus 56 in the first two weeks of March 2019, a 3x increase instead of the 14x increase reported by Bergamo News.

Bergamo’s hospital had 16 beds in its intensive care unit, in line with international standards (it is typical to have of the order of an ICU bed per 5000-10,000 people, and Bergamo has a population of 120,000). Right now there are 80 people in intensive care in Bergamo, a 5x increase in capacity that was possible by bringing in a lot of ventilators and moving other sick people to other hospitals. Nonetheless, there have been reports of shortages of ICU beds, and of people needing to intubated that could not be. There are also reports of people dying of pneumonia at home, without being tested.

Because of this surge in deaths, Bergamo’s funeral homes have not been able to keep up. It’s not that they have not been able to keep up with arranging funerals, because funerals are banned. They just do not have the capacity to perform the burials.

So coffins have been accumulating. A couple of days ago, a motorcade of army vehicles came to Bergamo to pick up 70 coffins and take them to other cities.

It should be noted that this is happening after 20 days of “social distancing” measures and after 13 days of “sheltering at home” in Lombardy.

My point being, if we had not known that a news virus was going around, the number of excess deaths in Bergamo would have not been hidden by the random noise in the number of deaths due to influenza-like illness.

The Early Years of Computing in Italy

Here are in theory‘s first ever book reviews! The books are

Giorgio Garuzzo
Quando in Italia si facevano i computer
Available for free at Amazon.com and Amazon.it.

Giorgio Ausiello
The Making of a New Science
Available from Springer, as a DRM-free PDF through your academic library.

Both books talk about the early years of computing in Italy, on the industrial and academic side, respectively. They briefly intersect with the story of Olivetti’s Elea computer.

And now for something completely different

After 22 years in the United States, 19 of which spent in the San Francisco Bay Area, this Summer I will move to Milan to take a job at Bocconi University.

Like a certain well-known Bay Area institution, Bocconi is a private university that was endowed by a rich merchant in memory of his dead son. Initially characterized by an exclusive focus on law, economics and business, it has had for a while a high domestic recognition for the quality of teaching and, more recently, a good international profile both in teaching and research. Despite its small size, compared to Italy’s giant public universities, in 2017 Bocconi was the Italian university which had received the most ERC grants during the first ten years of existence of the European Research Council (in second place was my Alma Mater, the Sapienza University of Rome, which has about nine times more professors) (source).

About three years ago, Bocconi started planning for a move in the space of computing, in the context of their existing efforts in data science. As a first step, they recruited Riccardo Zecchina. You may remember Riccardo from his work providing a non-rigorous calculation of the threshold of random 3-SAT, his work on the “survey propagation” algorithm for SAT and other constraint satisfaction problems, as well as other work that brought statistical physics techniques to computer science. Currently, Riccardo and his group are doing very exciting work on the theory of deep learning.

Though I knew of his work, I had never met Riccardo until I attended a 2017 workshop at the Santa Fe Institute on “Thermodynamics and computation,” an invitation that I had accepted on whim, mostly based on the fact that I had never been to New Mexico and I had really liked Breaking Bad. Riccardo had just moved to Bocconi, he told me about their future plans, and he asked me if I was interested. I initially politely declined, but one thing led to another, and now here I am putting up my San Francisco house for sale.

Last August, as I was considering this move, I applied for an ERC grant from the European Union, and I just learned that the grant has been approved. This grant is approximately the same amount as the total of all the grants that I have received from the NSF over the past twenty years, and it will support several postdoc positions, as well as visitors ranging from people coming for a week to give a talk and meet with my group to a full-year sabbatical visit.

Although it’s a bit late for that, I am looking for postdocs starting as early as this September: if you are interested please contact me. The postdoc positions will pay a highly competitive salary, which will be free of Italian income tax (although American citizens will owe federal income tax to the IRS correction: American citizens would not owe anything to IRS either). As a person from Rome, I am not allowed to say good things about Milan or else I will have to return my Roman card (it’s kind of a NY versus LA thing), but I think that the allure of the city speaks for itself.

Likewise, if you are a senior researcher, and you have always wanted to visit me and work together on spectral methods, approximation algorithms, graph theory or graph algorithms, but you felt that Berkeley had insufficiently many Leonardo mural paintings and opera houses, and that it was too far from the Alps, then now you are in luck!

Alessio Figalli Explains the Isoperimetric Problem

Starts at 2:00

Corrado Bohm

I was very saddened to hear that Corrado Böhm died today at age 94.

Böhm was one of the founding fathers of Italian computer science. His dissertation, from 1951, was one of the first (maybe the first? I don’t know the history of these ideas very well) examples of a programming language with a compiler written in the language itself. In the 1950s and 1960s he worked at the CNR (an Italian national research institution with its own technical staff), in the IAC (Institute for the Applications of Computing) directed by mathematician Mauro Picone. IAC was the second place in Italy to acquire a computer. In 1970 he moved to the University of Turin, were he was the founding chairman of the computer science department. In 1972 he moved to the Sapienza University of Rome, in the Math department, and in 1989 he was one of the founders of the Computer Science department at Sapienza. He remained at Sapienza until his retirement.

Böhm became internationally known for a 1966 result, joint with Giuseppe Jacopini, in which he showed, roughly speaking, that programs written in a language that includes goto statements (formalized as flow-charts) could be mapped to equivalent programs that don’t. The point of the paper was that the translation was “structural” and the translated program retained much of the structure and the logic of the original program, meaning that programmers could give up goto statements without having to fundamentally change the way they think.

Dijkstra’s famous “Go To Statement Considered Harmful” 1968 letter to CACM had two references, one of which was the Jacopini-Böhm theorem.

Böhm was responsible for important foundational work on lambda calculus, typed functional languages, and the theory of programming languages at large.

He was a remarkable mentor, many of whose students and collaborators (including a notable number of women) became prominent in the Italian community of theory of programming languages, and Italian academia in general.

In the photo above is Böhm with Simona Ronchi, Betti Venneri and Mariangiola Dezani, who all became prominent Italian professors.

You may also recognize the man on the right as a recent recipient of the Turing Award. Silvio Micali went to Sapienza to study math as an undergrad, and he worked with Böhm, who encouraged Silvio to pursue his PhD abroad.

I studied Computer Science at Sapienza, starting the first year that the major was introduced in 1989. I remember that when I first met Böhm he reminded me of Doc Brown from Back to the Future: a tall man with crazy white hair, speaking of wild ideas with incomprehensible technical terms, but with unstoppable enthusiasm.

One year, I tried attending a small elective class that he was teaching. My, probably imprecise, recollection of the first lecture is as follows.

He said that one vertex is a binary tree, and that if you connect two binary trees to a new root you also get a binary tree, then he asked us, how would you prove statements on binary trees by induction? The class stopped until we would say something. After some consultation among us, one of the smart kids proposed “by induction on the number of vertices?” Yes, said Böhm, that would work, but isn’t there a better way? He wanted us to come up by ourselves with the insight that, since binary trees have a recursive definition, one can do induction on the structure of the definition.

In subsequent lectures, we looked (without being told) at how to construct purely functional data structures. I dropped the class after about a month.

(Photo credits: corradobohm.it)