This is San Francisco

A truck selling mini-cupcakes is parked in the Castro and doing business. It has its Twitter feed printed on the side. By subscribing to the mini-cupcakes truck Twitter feed, you can know in advance when it’s in your neighborhood. Or, if so inclined, you can follow it around the city.

A large man with a tiny dog looks at the cupcakes, then he turns to the tiny dog. “Would you like a cupcake?” he asks the dog, “remember when you had cupcake last time, you liked it.” The dog is not making eye contact with the man. “So, do you want a cupcake, or not? Tell me.”

Academic Kakistocracy

Via Izabella Laba and Crooked Timber, I have found this very interesting book review by Scott McLemee of Diego Gambetta‘s book Codes of the Underworld: How Criminals Communicate.

Gambetta, a professor of sociology at Oxford, has studied the problem of trust from a game-theoretic perspective, and he considers the issue of signaling in trust games. Signaling is a process in which a party in a game-theoretic setting indicates that he is going to follow a certain strategy. For example, it is well known that a way to win a game of chicken is to visibly rip off your steering wheel and wear a blindfold. Then your opponent will see that there is no way you can steer, and so he will steer. (Cf. Bush administration foreign policy.)

In the book, Gambetta considers trust in criminal organizations, in which one cannot rely on the rule of law to enforce compliance. He posits that a signaling strategy for members of crime organizations is to signal incompetence; the logic being that if you are unable to do anything else, then you are not going to try to go ‘legit’ and so (i) you are not a threat to the businesses that you are shaking down of eventually becoming a competitor, and (ii) you are reliant on the crime organization to provide for your livelihood and so you are not going to antagonize it.

Perhaps tongue-in-cheek, Gambetta goes on to explain how this applies to Italian academia. I don’t have to book, so I quote McLemee as he quotes Gambetta:

Gambetta argues that something similar takes place among the baroni (barons) who oversee the selection committees involved in Italian academic promotions. While some fields are more meritocratic than others, he says, the struggle for advancement involves a great deal of horse trading. “The barons operate on the basis of a pact of reciprocity, which requires a lot of trust, for debts are repaid years later. …The most powerful figures in this system, says Gambetta, tend to be the least intellectually distinguished. … “… and this is what is the most intriguing, they do not try to hide their weakness. One has the impression that they almost flaunt it in personal contacts.” … Gambetta argues that the cheerful incompetence of the baroni is akin to the mafioso’s way of signaling that he can be “trusted” within his narrowly predatory limits.

“Being incompetent and displaying it,” he writes, “conveys the message I will not run away, for I have no strong legs to run anywhere else. In a corrupt academic market, being good at and interested in one’s own research, by contrast, signal a potential for a career independent of corrupt reciprocity…. In the Italian academic world, the kakistocrats are those who best assure others by displaying, through lack of competence and lack of interest in research, that they will comply with the pacts.”

The comments at Crooked Timber are also worth reading.

Good Reads

Arora, Barak, Brunnermeier and Ge have a new paper showing that it is possible to construct “toxic” financial derivative products such that detecting the bad assets is computationally intractable and even proving that a fraud has been committed is impossible. The paper gets a mention in BoingBoing.

The book “Concentration of Measure for the Analysis of Randomized Algorithms” by Dubhashi and Panconesi is out, and is fantastic.

It starts with the basic Chernoff-Hoeffding bounds: if X_1,\ldots,X_n are independent bounded random variables, each ranging in [0,1], then

Pr [ |  \sum_i X_i - {\mathbb E} \sum_i X_i | \geq t ] \leq 2 e^{-2t^2/n}

and similar bounds hold also if the X_i have bounded variance.

In many applications, however, one may have to deal with random variables X_1,\ldots,X_n which are correlated, and with operations that are more complicated than sums. For example, suppose we want to prove that there are expanding d-regular graphs. Then we may try to apply the probabilistic method, and generate a d-regular graph by picking d random matchings and taking the union, then showing that for every cut k \leq |V|/2, and every subset of k vertices, the probability that the set of vertices is non-expanding is much less than {|V| \choose k}, so even summing over all sets we have probability less than one that the graph is non-expanding. The difficulty is how to reason about the number of edges leaving a set of size k in a process in which we pick d random matchings. Each of the d|V|/2 edges we generate has probability 2\cdot k \cdot (|V|-k) / |V|^2 of leaving the set, but these d|V|/2 events are not independent.

Usually, Azuma’s inequality is powerful enough to deal with such dependencies and recover a bound. In many interesting cases, however, the assumptions of Azuma’s inequality are not met, and one has to work with more powerful tools, such as Talagrand’s inequality, which is also covered in the book. Finally, in extreme cases, one may have to resort to log-Sobolev inequalities, which I have never had a chance to understand so far, and even they get a very clear treatment.

The book has its quirks. Lemma 2.3, for example, has a handwritten proof, attributed to Anupam Gupta’s penmanship.

Many Happy Returns

The PRC celebrated its 60th birthday on Thursday. After the many man-made disasters of the 1950s, 60s and 70s, the quality of life of apolitical Han Chinese living in big cities has been improving dramatically in the past seventeen years. Now if only they can reduce pollution, rein in corruption, establish an independent judiciary, allow freedom of expression, religion, and association, reverse the ethnic and cultural dilution of minority regions, and lift the quality of life of rural areas, the 100th birthday will be a truly joyous occasion.

This is the funniest commentary I have found on the festivities. The references to Hu Jintao will not make sense unless you watch this video

Bob Herbert on UC Berkeley

Tomorrow’s New York Times has an op-ed by Bob Herbert on the funding crisis at U.C. Berkeley. He makes the important points about the uniqueness of Berkeley in giving top-quality education (and a good chance to move on to grad school) to students of very diverse backgrounds, serving working class and middle-class students like no other top university. He also makes the following, very important, point

[The changes caused by the budget crisis] would most likely hurt students from middle-class families more than poorer ones. Those kids are caught between the less well-off, who are helped by a variety of financial aid programs, and the wealthy students, whose families have no problem paying for a first-class college education.

The Nobel Laureate and the Dropout

Italian Minister for economic development Claudio Scajola (pronounced sky-olah) is in America for the week. He met his counterpart (Scajola is in charge, among other things, of energy policies) Steven Chu on Tuesday, and he signed a five-years agreement on nuclear energy research and development. (Italian voters rejected the use of nuclear energy in Italy 22 years ago, in a referendum that the government is planning to overrule.) It says something of the Berlusconi versus the Obama administrations that Scajola is a college dropout and Chu is a Nobel Laureate. Scajola then met Italian entrepreneurs in New York and in Detroit, and a bit of research turned out this embarrassing infomercial which was actual “journalistic” reporting from one of the two major Italian broadcast news program (on a Berlusconi-owned channel).

Finally, today, he arrived in San Francisco and this evening there was a reception in his honor at the Italian Consulate, to which I was invited for reasons that are not entirely clear (more later).

After dropping out of college, Scajola became mayor of his hometown, of which his father and brother had been mayors earlier. He resigned among corruption charges, then resurfaced as member of parliament for the Democrazia Cristiana, the dominant party in Italy from the end of WW2 to the early 1990s. When the party started crumbling under widespread corruption investigations, Scajola was one of the first to jump ship to the new party that Berlusconi was creating. He was in charge of the day-to-day operations for several years, and eventually was promoted minister of the interior. This is one of the highest profile cabinet positions, because the holder is in charge of Italian law enforcement and civilian security forces. When the 2002 Group of 8 meeting took place in Genoa, one of the demonstrators was shot dead, and widespread illegal detentions and abuses against demonstrators took place. No high-ranking official of the Italian police forces was indicted for the abuses. Later in 2002, Marco Biagi, a professor and government consultant for labor reform, was killed by domestic terrorists. In an infamous interview, Scajola was asked why Biagi was not under police protection, being a key player in certain tense labor negotiations. Scajola replied “ma quale figura centrale, Biagi era solo un rompicoglioni.” After that, he had to resign. He was back in the government in 2003.

Anyways, I am not one to turn down free drinks or the premise for a good story, so off I went to the lovely Pacific Heights Italian Consulate and mingled with A-list Italians. The one person I talked to was a Stanford professor of Architecture who knew my colleague Alberto Sangiovanni-Vincentelli, and who told me that in Japan they can construct buildings entirely with robots, no humans needed. So there I was drinking my free prosecco, wondering about the Japanese robots, and satisfied with the token of appreciation for scholarship implied by my presence there. Until, that is, Scajola made his speech and explained how he had just been to “Silicon Valley” for a roundtable discussion with Italian “researchers and entrepreneurs,” that I hadn’t been invited to. So, in the eyes of the Consulate, I am one to invite to parties but not one to talk to about research. Come to think of it, I am not sure if I should be flattered or offended.