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.

Yesterday, Bloom and Sisask posted a paper in which they show that there is a constant such that, for every sufficiently large , if has cardinality at least , then contains a non-trivial length-3 arithmetic progression. Without context, this may seem like a strange result to get excited about, but it sits at the nexus of a number of fundamental results and open questions in combinatorics. Gil Kalai has written an excellent post telling the story of this problem, so instead of writing a worse version of it I will refer the reader to Gil’s blog.

Back to bad news, the day after Harvard announced that it would deliver courses online only in 2020-21, the Trump administration announced that it would void student visas of students who are not attending in-person classes in 2020-21. Back to good news, Harvard and MIT announced that they will sue the federal government over this, and other universities, including the University of California system, are planning similar responses. Apart from the action, I was really heartened to read MIT’s President statement on the matter (thanks to Vinod Vaikuntanathan for bringing it my attention) which is worth reproducing:

To the members of the MIT community,

On Monday, in a surprising development, a division of Immigration and Customs Enforcement announced that it will not permit international students on F-1 visas to take a full online course load this fall while studying in the United States. As I wrote yesterday, this ruling has potentially serious implications for MIT’s international students and those enrolled at institutions across the country.

This morning, in response, MIT and Harvard jointly filed suit against ICE and the US Department of Homeland Security in federal court in Massachusetts. In the lawsuit, we ask the court to prevent ICE and DHS from enforcing the new guidance and to declare it unlawful.

The announcement disrupts our international students’ lives and jeopardizes their academic and research pursuits. ICE is unable to offer the most basic answers about how its policy will be interpreted or implemented. And the guidance comes after many US colleges and universities either released or are readying their final decisions for the fall – decisions designed to advance their educational mission and protect the health and safety of their communities.

Our international students now have many questions – about their visas, their health, their families and their ability to continue working toward an MIT degree. Unspoken, but unmistakable, is one more question: Am I welcome?

At MIT, the answer, unequivocally, is yes.

MIT’s strength is its people – no matter where they come from. I know firsthand the anxiety of arriving in this country as a student, excited to advance my education, but separated from my family by thousands of miles. I also know that welcoming the world’s brightest, most talented and motivated students is an essential American strength.

While we pursue legal protections for our international students, we will continue to stay in close touch with them through email and updates on the International Students Office’s website. If you have questions, you may write to the ISO at iso-help@mit.edu.

Sincerely,

L. Rafael Reif

This way of talking like a human being, and like you actually care about the matter at hand, is a big contrast with the robotic statements that usually come out of campus leadership. The corresponding message from UC Berkeley’s Chancellor is the way such statements usually are like:

Dear campus community,

Yesterday, the Department of Homeland Security issued new guidance to universities related to international students and fall instruction requirements. The guidance is deeply concerning: it could potentially force the return of many international students to their home countries if they are unable to find the appropriate balance of in-person and remote classes. These requirements run counter to our values of being an inclusive community and one that has a long tradition of welcoming international students from around the globe. International students enrich campus life immeasurably, through their participation in classes, research collaborations and extracurricular activities.

We will explore all of our options, legal and otherwise, to counter the deleterious effects of these policies that imp act the ability for international students to achieve their academic goals. It is not only important for UC Berkeley but for all of higher education across the U.S. to take every step possible to mitigate these policies that send a message of exclusion to our international community of scholars. We will partner with our professional associations to advocate for sound legislation that continues to support international educational exchange.

More immediately, we are working with colleagues across our campus to identify a path that will allow us to comply with these requirements while ensuring a healthy learning environment, and paying attention to the needs of our international students. We recognize the concern and anxiety these new rules have created, and we are moving quickly to ensure that we offer the proper balance of online and in-person classes so that our students can remain in the U.S. and satisfy their visa requirements, and that those students residing outside the U.S. can maintain their enrollment status.

We expect to announce more details soon. Should you have any questions, please contact the Berkeley International Office at internationaloffice@berkeley.edu.

Sincerely,

Carol Christ
Chancellor

Lisa Alvarez-Cohen
Vice Provost for Academic Planning and Senior International Officer

It is interesting to think about where this difference in tone is coming from. Carol Christ is a renown humanities scholar who, I suppose, writes well. She comes across as charismatic and caring, and she is definitely straight-talking in person. Probably, as for everything else, Berkeley has a byzantine process to create announcements and press releases, and if Stephen Colbert was the Chancellor of UC Berkeley, after a couple of weeks on the job he would sound just as deeply concerned and just as into exploring all options, while meanwhile working to identify a path and paying attention about something that is totally fucked up and needs action today.

Which brings me to all the statements in support of Black Lives Matter that have been coming out of every scholarly institution in the last few days. While their messages are generally unobjectionable, there is a certain sameness to their form (“we say their names…”, “we will do the work…”, “we see you…”) and they don’t sound at all like the way the people putting them out speak. This has complicated causes, including the fact that many such statements came out of letter-writing campaigns that demanded statements in a very specific way, without leaving a lot of room for individual expression. The association of American Poets, for example, put out a statement of solidarity with the Black community; in response, a letter with 1800 signatories claimed that it was too weak a statement and that it was, in fact, itself an act of violence against Black people; several resignations followed. The Board of the National Book Critics Circle was working on such a statement, and the work devolved into acrimony and several rounds of “I am outraged and I resign,” “no I am outraged at your outrage and I resign, “well then I am outraged that you are outraged at her outrage” until almost the whole board was gone in a “sequence of events [that] was bizarre and bloody in an end-of-a-Tarantino-movie way.”

Also, people in America talk about race the way UC Berkeley administrators talk about anything, that is extremely carefully and vacuously. But, back to the statements about foreign students, the difference between the administrative cultures at MIT and Berkeley is not the only difference between the statements of Reif and Christ: clearly a big difference is that Reif is an immigrant himself. When Trayvon Martin was killed, Obama talked about the killing in a way that was very different, and much more meaningful, than other politicians: if I had a son, Obama said, he would look a lot like Trayvon. If there were more people of color in positions of academic leadership, I think that we would have seen an academic response to Black Lives Matter that would have been less fearful, dogmatic and robotic and more meaningful and productive. Or perhaps we would have all ended up like the National Book Critic Circle, it’s hard to say.