Is that like NP-completeness?

Every month, Berkeley’s Chancellor Birgeneau invites a group of about a dozen randomly chosen faculty for lunch. Today, I was picked.

Birgeneau had visited the EECS department once. He came to our faculty lunch, and gave a fairly standard prepared talk on excellence, public service and the usual stuff, but I really liked the way he answered questions afterwards. One question was on interdisciplinary science. I thought he was going to say something about big science for the 21st century, but, instead, he said that interdisciplinary studies are great and important, but one should not forget that science advances also because of the scientist who sits alone in her office and solves a 40-year old problem, and that, for him, it was very important that these kind of advances happen in Berkeley. I was flabbergasted. One can say such things and become Chancellor? Amazing.

The faculty invited at the lunch is in accordance with the Birthday Paradox. Berkeley has about 100 departments, nine randomly chosen people showed up, and two of them were from the same department. I manage to refrain from pointing it out. I notice that one of us is a white woman, one is an Asian man, and the rest are white men. We sit down, and we go around the table introducing ourselves. “I study labour movements in South America,” “I study the Renaissance period in Italy and Spain, and especially the history of the Colonna family in Rome,” “I study silent movies from the 1920s and 1930s in Slavic languages, especially Russian cinema.” It’s up to me. “I work in computer science, and my interest is in an area of theoretical computer science called computational complexity.” Eyes begin to roll. “We study why certain problems are impossible to solve using computer programs.” People smile politely at our folly. “Or, actually, they could be solved in principle but, by any method, it would take such an astronomical long time that it is essentially impossible.” People look relieved that my introduction is over.

“Oh” says Birgeneau “is that like NP completeness?” I nod. “And do you study quantum algorithns for these problems?” No, but some of my colleagues do. Wow, take that, scholar of the Colonna family!

The last to introduce themeselves are the two economists, sitting next to each other. One of them is a theoretician, working on econometrics and, specifically, on statistical methods. Birgeneau asks him about relations between theory and practice. “As an economist” he replies brilliantly “I favor the division of labor.” Then Birgeneau asks me about theory and practice. I dodge the question and talk about the computational point of view on economics, and I do my duty for the evangelization of the virtues of the computational perspective in general.

I had prepared two grievances that I was going to air, but the conversation takes a different turn. Birgeneau says that at each lunch there are always two or three people who use the occasion to voice complaints. He did not say it like it was a good thing, so, in this particular lunch, nobody does.

The conversation turns to Berkeley’s main failure: diversity. Berkeley has a terrible record in attracting students from underrepresented groups, and it is Latino students who are the worst served. Latinos are a substantial fraction of the California population, and a very small fraction of Berkeley students. Student groups are very vocal in asking for something to be done about it, and he is very receptive. The main roadblock to any progress, however, is Proposition 209. On this matter, he has something very interesting to say. Proposition 209 passed by 400,000 votes. In California, there are about 4 million Latinos who are not registered to vote. A voting-registration initiative could prepare the terrain for a repeal of Proposition 209, and it should be student groups who should lead such an initiative. So, apparently, this is what he always says to the protesting students. When they ask him what he is doing to increase minority representation, he asks them what they are doing to repeal Proposition 209.

About these ads

7 thoughts on “Is that like NP-completeness?

  1. It is quite surprising why it is socially acceptable to find the study of computability boring, but one has to feel that esoteric social studies about the history of a certain family in 17th century is interesting. It would seem to me that the study of what can be computed and what cannot be is fascinating! I still remember the time when I first heard of the halting problem — I was in high school then — and how impresseded I was that one could show it is not decidable.

    But then again, I am a computer scientist and there is a reason why.

  2. I personally find history very interesting, and I singled out the Colonna scholar because I thought his subject was the coolest. Also, I exaggerated my colleagues’ reactions for comic effect.

    Why is it acceptable, in polite company, to be bored by (or ignorant of) science, math and engineering? That’s an important and difficult question. I plan to write about it, even though, of course, I have nothing new to say.

  3. As a clarification — I find history interesting too, and my intent was not to say that the study of 17th century Italy is boring. What I meant is that to a non-expert, the study of the Colonna family in 17th century Italy is just as specialized as the study of average-case complexity. Noone in polite company would admit to finding the former boring, but many would claim to find the latter so.

  4. I must apologize in advance, but I can’t stand it anymore.

    “40-years old problem” should read “40-year-old”. Similarly, “eight-man boat” and “five-hour drive”. On the other hand, you can say “a five hours’ drive” (but not “a five-hours drive”) because you can say “a drive of five hours”. You can also say “a one-hour drive” and “an hour’s drive”.

    Otherwise, keep up the good work.

  5. I just want to heap arbitrary praise on your blog, and this seems to be as good a place to do it as any. Are you aware of how excellent it is, Luca? It is already one of the most satisfying things I read online, and always brings a smile to my face. I went to Berkeley, and study theory, so I’m certaintly the intended niche audience. But still… Thanks! I’ll say something more substantial next time.

  6. The biggest minority in California are hispanos. Estamos aquí antes que ustedes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s