七夕快乐!

Happy Qi Xi festival, everybody. This is the “Chinese Valentine’s day,” which falls on July 7th on the lunar calendar, which this year is August 20th. The festivity relates to a story that, like many Chinese stories, is a pretty long story.

The gist of it is that the (seventh) daughter of a goddess at some point came to earth to live as a mortal and met a cowboy (as in, a guy whose job is to herd cows). The two fell in love, got married, had two children (I told you, it’s a long story) and they were pretty happy, until the goddess mom realized what happened.

As is mothers-in-law’s wont, she did not approve, and she recalled the daughter to heaven, where she is now the star Vega. The guy was desperate, but then one of his cows suggested that he kills it, and then use its skin to fly to heaven (don’t ask) and reunite with his wife.

He does so, and it works, so that he is now the star Altair, but then the mom-in-law found out again. So she created a river, the Milky Way, to separate them once more. And now they are forever separated, except that, every year, magpies (which are a kind of crows) fly to heaven and use their bodies to create a bridge over the Milky Way, so that the two lovers can use it to meet. And this happens on the 7th day and the 7th month of the year.

What a difference thirty years make

From the majority opinions of two rulings of the Supreme Court of the United States.

Bowers v. Hardwick (1986):

The Constitution does not confer a fundamental right upon homosexuals to engage in sodomy. […] to claim that a right to engage in such conduct is “deeply rooted in this Nation’s history and tradition” or “implicit in the concept of ordered liberty” is, at best, facetious.

Obergefell v. Hodges (2015)

[Same-sex couples] ask for equal dignity in the eyes of the law. The Constitution grants them that right. The Constitution […] does not permit the State to bar same-sex couples from marriage on the same terms as accorded to couples of the opposite sex.

the future of the Conference on Computational Complexity

As you may remember, a few months ago Dieter van Melkebeek, the steering committee chair of the conference on computational complexity, started a discussion on the future of the conference and on its relation to IEEE.

A poll among CCC former participants showed that 97% of respondents favored change, and a majority wanted the conference to be independent of both IEEE and ACM. The steering committee, subsequently, voted unanimously to make the conference independent.

The steering committee is now working out the logistics, and volunteers are needed to help. Already several people have pledged to contribute in various forms, and if you are interested there will be organizational meetings in Vancouver during CCC 2014. (By the way, today is the deadline for early registration.)

I would like to publicly thank Dieter both for the effort that he put on making this change happen and for the transparency of the process. I hope that, if some big change is coming for STOC or FOCS, it will be the result of a similarly open discussion.

Ora e sempre resistenza

Today it’s my favorite of Italy’s public holidays.

To keep a long story long, at the start of WW2, Italy, which was an ally of Germany, was initially neutral, in part because its armed forces were completely unprepared for war. At some point in the May of 1940, with German troops advancing into France, and British troops evacuating the continent, Italy decided to join what looked like a soon-to-end war, in order to claim some French territories and colonies.

But then, in 1941, Germany attacked Russia and Japan attacked the US, underestimating what they were getting into, and by the beginning of 1943 the tide was clearly turning against the “axis.” Italy’s king, who was definitely not the “fight until the last man” type, had Mussolini arrested, installed a general as prime minister, and started negotiating Italy’s surrender with the allies (even as Italian troops were fighting with the Germans in Russia and in Africa). Eventually, on September 8, 1943, the king announced a cease-fire. Because of the secrecy of the negotiations, nobody knew what was going in advance, and most of the Italian troops that were fighting with the Germans were taken prisoners, while the rest of the armed forces basically disbanded. German troops came into Italy from the North to occupy it, even as allied troops landed in Sicily and took control of most of Southern Italy. The king fled to the South, and the Germans freed Mussolini and installed him as head of a puppet government in the North.

With the Italian army disbanded, and with the allies neglecting the “Southern front” in Italy as they were plotting the landing in Normandy, guerilla groups were formed in Northern Italy to fight the Germans. Eventually, in April 1945 the German troops were retreating from the Eastern and Western fronts against the advancing American and Russian forces, and the allied made another push in Italy; concurrently, the resistance organizations planned an insurrection that, on April 25, liberated Torino and Milan. All the German forces in Italy surrendered on April 29.

The resistance was the training ground of some of the first generation of politicians of the new Italian Republic (a referendum to abolish the monarchy passed in 1946, and a new Republican constitution was approved in 1948), and it brought people who were willing to die for their ideals into politics. That spirit didn’t last very long, but it remains one of the few bright spots in recent Italian history.

Holiday Readings

Now that the Winter break is coming, what to read in between decorating, cooking, eating, drinking and being merry?

The most exciting theoretical computer science development of the year was the improved efficiency of matrix multiplication by Stother and Vassilevska-Williams. Virginia’s 72-page write-up will certainly keep many people occupied.

Terence Tao is teaching a class on expanders, and posting the lecture notes, of exceptional high quality. It is hard to imagine something that would a more awesome combination, to me, than Terry Tao writing about expanders. Maybe a biopic on Turing’s life, starring Joseph Gordon-Levitt, written by Dustin Lance Black and directed by Clint Eastwood.

Meanwhile, Ryan O’Donnell has been writing a book on analysis of boolean function, by “serializing” it on a blog platform.

Now that I have done my part, you do yours. If I wanted to read a couple of books (no math, no theory) during the winter, what would you recommend. Don’t recommend what you think I would like, recommend what you like best, and why.

A Genius Writes on China and Colorado

Although I was disappointed that, this year, the MacArthur foundation did not recognize any theoretical computer scientist or pure mathematician, I was delighted that Peter Hessler is one of this year’s fellows.

Hessler used to be the New Yorker’s correspondent from China, and he wrote a number of extraordinary articles from there. His masterpiece is probably the one about getting a Chinese driver’s license, which became the starting point of a book. Last year, he moved back to America, to Colorado, and wrote a great article about moving (as unlikely as that sounds), and he has been reporting from Colorado since.

The basics of great non-fiction storytelling are having a good story and telling it well. Surely, Hessler can write, but what about the stories themselves? Living in a hutong, getting a driver’s license, traveling alone in the Chinese countryside, and so on, are all ways to make interesting things happen, but a story is more than a series of interesting things that happened. Indeed, interesting things happen to all of us all the time, but it takes a rare sensibility to recognize the meaningfulness of small details and seemingly mundane events, which is where Hessler excels (see his article in this week’s New Yorker’s about a pharmacist in Colorado).

Those who read in theory probably also read Claire Mathieu‘s blog. Claire has this ability to an uncanny degree. If she was not so brilliant and successful as a computer scientist, I would say that it’s a waste that she is not a writer. If you are not familiar with her blog, read this post about squeezing toothpaste, and you’ll see what I mean.