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

They are perfect for each other

Now that Ted Cruz has chosen his running mate, everybody is wondering: who is going to be Trump’s pick for vice-president?

It would make sense if, to mitigate his negatives, Trump chose a person of color and someone who has a history of speaking out against income inequality.

He or she would have to be someone who is media-savvy and with some experience running a campaign, but definitely not a career politician. And of course he or she should be someone who endorsed Trump early on, like, say, in January.

Continue reading

On Berkeley and Recycling

For the past few days, I have been getting emails that are the Platonic ideal of the U.C. Berkeley administration.

Today, there was a one-hour presentation on recycling and composting at Soda Hall, the computer science building. This is worth saying once more: a one hour presentation on putting glass, metal, and certain plastics in one container, clean paper in another, and compostable material in a third one. We received an email announcement, then an invitation to add the event to our calendar, then two remainders.

But what if one cannot make it? Not to worry! There will be a second one hour presentation on recycling, for those who missed the first one, and for those that were so enthralled by the first one that they want to spend one more hour being told about recycling.

Meanwhile, I have been trying since February to get a desk, a conference table and a bookshelf for my office in Soda Hall. So far I got the desk.

I asked Christos what he thought about the two one-hour presentations on recycling, and he said it reminded him of a passage from a famous essay by Michael Chabon:

Passersby feel empowered-indeed, they feel duty-bound-to criticize your parking technique, your failure to sort your recycling into brown paper and white, your resource-hogging four-wheel-drive vehicle, your use of a pinch-collar to keep your dog from straining at the leash.

Sometimes I think that when the administration started hearing about MOOCs, they must have started to dream about a future with no professors, because the students all take MOOCs, and no students on campus, because they all take the MOOCs from their home, and the campus would just be filled by Assistant Chancellors of this and that, giving each other training workshops. And this would be like the episode of Get Smart in which Max infiltrates a criminal gang until he finds out that everybody is an infiltrator and there is no criminal left.

I almost fell for it

This year, the chair of ICALP decided to play an April Fool’s prank three weeks early, and I received the following message:

“Dear author, we regret to inform you that the margins in your submission are too small, and hence we are rejecting it without review”

I was almost fooled. In my defense, the second time that I applied for a position in Italy, the hiring committee judged all my publications to be non-existent, because the (multiple) copies I had sent them had not been authenticated by a notary. So I am trained not to consider it too strange that a paper could be evaluated based on the width of its margins (or the stamps on its pages) rather than on the content of its theorem.