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.

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.

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

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.

Three stories about U.C. administration

A few months ago, I was delighted to see the University of California holding on to its demands in its negotiations with Elsevier. The U.C. wanted to renegotiate its contract so that, in addition to having access to the subscribed journals, U.C. scholars could publish in them with open access (that is, so that anybody in the world would have free access to the articles written by U.C. scholars).

This seemed like a reasonable model to balance profitability for publishers and open access, but there was no way to agree on it with Elsevier. Meanwhile, U.C. has not renewed its Elsevier subscriptions and Elsevier has cut off access to U.C. libraries.

I was very impressed to see the University of California central administration do something right, so I wondered if this was the kind of portent that is a harbinger of the apocalypse, or just a fluke. Subsequent events suggest the latter.

The University of California has spent a lot of time and money to build a centralized system for job applications and for job applicant review. I was first made aware of this when I chaired the recruiting committee for the Simons Director position. At first we were told that we could solicit applications through the (vastly superior) EECS-built system for job applications and reviews. After the application deadline passed, we were told that, in fact, we could not use the EECS system, and so the already overworked EECS faculty HR person had to manually copy all the data in the central campus system.

The American Mathematical Society has created a wonderfully functional system, called Mathjobs where applicants for academic mathematics jobs (ranging from postdocs to professorship) can upload their application material once, and their recommenders can upload their letters once, and then all the universities that the candidate applies to have access to this material. Furthermore, if needed, both applicants and recommenders can tailor-make their material for a particular university or universities, if they want to.

Everybody was living happily, but not ever after, because the U.C. central campus administration decided that everybody in the University of California had to use the centralized system for all jobs. Both the AMS and U.C. mathematicians tried to find a reasonable accommodation, such as allowing the U.C. system to access the letters posted on mathjobs. The campus administration reasoned response was roughly “sucks to be you.” There is more of the story in an AMS notices article by the chair of math at U.C. Davis.

Finally, this year U.C. Berkeley will not be listed in the US News and World Report rankings because it has submitted wrong data in the past.

ما همه ایرانی

Many people are angry and heartbroken at the consequences (on themselves, their loved ones, their friends and coworkers) of the executive order that has banned refugees, as well as legal immigrants and green card holders, from certain countries from entering the US for the next few months. A common question is, what can we do? A few possibilities:

  • Donate to the ACLU. They have a long history of fighting for civil rights and, on Saturday, they immediately sprung into action and where able to get a stay on the ban, whose implications are still not clear.
    As you are contemplating donations, consider also supporting Planned Parenthood and the Southern Poverty Law Center. This is unrelated to the current refugees/immigrant crisis, but it is relevant to what will probably be future crises instigated by the current administration. (The SPLC does a great work in tracking and documenting hate groups.)
  • Sign this petition, which has received significant media coverage
  • Do what you can to make sure our professional societies produce a response. Both the outgoing and the incoming presidents of the AMS have signed the above petition, and I understand that the appropriate committee of the AMS  is considering making a statement. I don’t know if the ACM is planning a similar action, and if you have access to the ACM leadership, please lean on them to do so.
    (Edited to add: ACM put out a statement Monday morning, and so this the AMS.)
  • Call your representatives in congress, especially if you live in a state with Republican senators or in a district with a Republican representative. Don’t email: call and ask to speak with the staffer who is responsible for immigration matters.
  • Reach out to colleagues, students and staff who are affected by the executive order. If you have channels to do so, pressure campus leadership to cover their legal expenses, which could be substantial.

If you have other ideas, please share them in the comments.

The vocabulary is political

Remember when the (GW) Bush administration decided that torture should be called “enhanced interrogation techniques,” and then the New York Times, like all other American news sources, started to call torture “enhanced interrogation techniques,” and people wrote angry letters to the public editor, and the public editor eventually wrote that if the White House decides that torture should not be called torture then calling torture torture is a political issues on which reporters should not take sides?

And Paul Krugman wrote a column in which he said that if the Bush administration declared that the Earth is flat, then the New York Times would have an article headlined “Roundness of Earth disputed,” in which it would make sure to have quotes both from round-Earther and flat-Earther?

Part of the reason for all this, as explained in this very good article in The Atlantic, is that political reporters (as opposed to political opinion writers) need access, that is, they need White House officials to talk to them, whether on the record or off the record. The ability to withhold access gives administration officials great leverage.

And so Myron Ebell, who works in a think-tank financed by the coal industry, and according to whom climate change is a vast conspiracy perpetrated by left-wing scientists, some of which scientists he has personally attacked, and who is being considered to lead the EPA, is now a climate contrarian, according to the New York Times.

Maybe soon enough, outside the opinion page, the New York Times will start calling racism “race realism.”

We need to occupy unsafe spaces

Today an atmosphere of grief pervaded Berkeley, and a series of emails came from higher and higher up the chain of command, culminating with one from Janet Napolitano, reaffirming the University of California’s commitment to its principles of inclusivity, diversity, and all things that are good. Here is an email from the Vice-Chancellor for Equity and Inclusion:

Dear Cal Students, Staff, and Faculty,

We know that the results of yesterday’s election have sparked fear and concern among many in our community; in particular our immigrant and undocumented communities, Muslim, African American, Chicanx/Latinx, LGBTQ+, Asian and Pacific Islander communities, survivors of sexual assault, people with disabilities, women, and many others. We are reaching out to you with a message of support. UC Berkeley leadership remains steadfast in our values and committed to the safety and well-being of all of our students, faculty, and staff. We condemn bigotry and hatred in all forms, and hold steadfast in our commitment to equity, access, and a campus that is safe, inclusive, and welcoming to all.

Various communities have organized the following community spaces and resources:

  • A community space for undocumented students tonight at 6:30pm in Chavez Room 105.
  • CLSD and CLPR are hosting space at the Shorb House, 2547 Channing Way from 12pm-5pm for students to come by. Faculty and staff will be there in community with our students for support.
  • MCC is holding a safe space for POC/Black students from 8pm-10pm this evening.
  • QTAP is hosting a QTOPC dinner in Anthony Hall at 6pm.
  • The Gender Equity Resource Center is open today, until 5pm, for those who wish for a quiet space for contemplation and community. GenEq is also hosting the following healing spaces:
    • Women’s Healing Space – Today, November 9th, 1pm-2:30pm
    • LGBTQ+ Healing Space – Today, November 9th, 2:30pm-4pm

Now, without discounting the value of having a good place to quietly sob with like-minded people, this strikes me as the message you would send after the Charleston shooting, or the Orlando shooting. This was not the act of one disturbed person. Sixty million Americans went to the trouble of going all the way to the polling place to vote for Trump, or of filling up their absentee ballot, and then mailing it in. That’s one in four adult Americans, a diverse coalition of white people: educated white people and less educated white people, male white people and female white people, religious white people and secular white people, and, one should note, even a few people who are not white. White people who thought it’s their constitutional right to discriminate against gay people, white people who think it’s ok to grab women by their pussy, and that you can get away with it if you are a star, white people who think muslims should not come to the US.

Our students will meet these people everywhere. They will be their neighbors, their coworkers, their bosses, and maybe their in-laws. When our students graduate, there will be no safe space.

And if there were, that is not where they should go. Because those sixty million people will not change their minds by talking among themselves.

But the oppressed cannot be left alone to speak out for themselves.

A feature of rape prevention programs is bystander intervention training: telling people how to recognize a situation in which someone is at risk of assault, and intervene.

We need white people to speak out against racism, christians to speak out for the religion freedom of non-christians, men to speak out against misogyny, straight people to speak out for LGBT people, Republicans to speak out against Trump.

And we need them to do this where it is not safe to do so, because otherwise all we have is angry people talking to the like-minded on the internet.

Edited to add a useful link