The \$325,000 washer-dryer

Only in New York.

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.

Welcome, Yonatan

You are a lucky kid.

Are you prepared?

It's the centennial of the great San Francisco earthquake of 1906. Last week, San Francisco residents received in the mail a pamphlet titled "are you prepared?"

The local Wallgreens is trying to capitalize on this, and there is a shelf with stuff that would be useful after a disaster. An "Are You Prepared?" sign hangs over the shelf.

Among other things, the shelf contains big jugs of aspirin, surgical masks, mechanical alarm clocks, first-aid kits, battery-operated radios, and so on.

What's with the mechanical alarm clocks? Why would I want to wake up early in the aftermath of a disaster?

The vision thing

Suresh asks what I think about "vision" in theory.

I have an instinctive (and irrational) dislike for this use of the word. It evokes to me images of people who are full of themselves, who say things like

"In the information age nonsense nonsense for the 21st century."

and who think that research can be planned in advance.

Thankfully, the theory community is quite immune to this kind of attitude. As theoreticians, we know that the only answer to the question "what will the great advances in theory be in the next five years" is "we don't know," because if we knew, we would be making these advances now, it would not take five years, and they would not be such great advances after all.

I shall still avoid the use of the loathed word, but I want to comment on the importance, for theoreticians, of perspective and taste.

I think it is very useful, for a theoretician, to develop her own "ideology" about theory: to get a sense of what she thinks are the long-term goals of the fields, of how a particular research program fits into these goals, and of what constitutes helpful progress. Without this perspective, one risks to end up studying a generalization of a special case of a problem related to a question that ... and so on.

It is also extremely important for the community itself to go through the process of defining such goals, and to explain the way in which current research fits them. Indeed, a story of goals understandable to a general educated public, and of the way we are making progress towards them, is very useful to funding agencies, where people charged with making difficult choices about assigning funds to different areas need to know what we are doing and what we need.

Here I should add two things. One, is that this "narrative" about what we do is not something that one person can sit down and write up in an afternoon, it is an extremely difficult, and never-ending, task in which the entire community must be actively involved. (See theorymatters.org.) The other, is that there need not be only a single way to think about theory, its motivations, and its goals. On the contrary, it would be a disaster if everybody was thinking in the same way, and several important results have come from the perseverance of researchers that had gone off in directions that others thought not promising. Presumably, there are at least two or three main, complementary, "ideologies" about theory, and all are worthy.

I have talked about the "strategic" way of thinking about research. At a "tactical" level, every research area has an infinite, or at least very large, number of well defined open questions, and a researcher needs "taste" to distinguish interesting questions from uninteresting ones. This is a particularly sensitive issue in complexity theory, where results typically don't have "applications" in any immediate practical sense. I think that there is a common misconception that complexity theorists like results that are difficult at the expense of results that are useful.

To understand complexity theorists' taste there are two things to keep in mind: that all the important open questions of complexity theory are far beyond our current techniques, and that the most exciting discoveries in complexity have been unexpected connections between different problems and surprising equivalences between models of computation. For both reasons, complexity theorists always look for new techniques and new questions, and a good problem is a problem that is understood to be just beyond (our understanding of) current techniques, and a good model is one that is not (known to be) equivalent to other models, and that captures interesting problems. This is, in part, the reason for the excitement around unique games and the reason why people seriously study the power of constant-depth circuits with mod-6 gates.

When a good question (one at the edge of the reach of known techniques) is solved, the proof is often very difficult, because the authors had to create from scratch something different, and often they did so in a way that was not the prettiest possible. Over time, however, the proofs of almost all important results in complexity theory have been cleaned up considerably. And when an important question is settled with a proof that is both novel and simple, I think everybody cheers twice.

Like for the broader perspective, I think it is very useful for a community to articulate its taste, to be able to explain why certain results and certain problems are important. This is even harder. At a gut level, I always know when I like something, but I find it extremely difficult to explain why, if someone asks.

The dreamy-eyed alumni

This busy week was not just about the FOCS deadline and paying taxes. Yesterday was also the deadline by which prospective graduate students had to choose which school they want to attend.

How do students make such a choice?

Theory students admitted to Berkeley have typically other excellent offers, and it is impossible for them to make a wrong choice. Wherever they end up, they will have very good advisors and a very conducive environment. I also think people overstate the impact of their choice in terms of career prospects: luck, good timing and talent are, I believe, the main factors that will matter, in this order. (I attribute my own job at Berkeley almost entirely to luck and flawless timing.)

But even though it is not as important as some people make it up to be, the choice of graduate school is still a choice that will dictate how you live for four to six years and, to a certain extent, what kind of theoretician you will become and what kind of taste you will develop. Unfortunately, it is a choice that is made based on very partial information: the impressions of a one-day visit, word-of-mouth, and the advice of professors at one's own institution.

So how do students choose to come to Berkeley? Perhaps their experience is not unlike mine when I had to decide whether to move here.

When I came to Berkeley for my interview, it was my first time on the West coast. All I knew about it were New Yorkers' preconceptions about California (people drive cars over there! And they shop in malls! It's like Long Island, but much much bigger) and what my Berkeley alumni friends told me of their experience.

Being a theoretician, I am friends with several people who were students at Berkeley, and I have always noticed how dreamy-eyed they become when they recall the time they spent here. This is very distinctive. Somehow, people don't become dreamy-eyed when recalling the time they spent as students at other places. This, of course, does not mean much. Think about your exes: X who was so nice, and that jerk/bitch Y. Now, did you have a better time with X or with Y? Did the relationship with X or the one with Y make you grow up more?

Anyways, everybody's sweet Berkeley memories were such that I arrived here prepared to be dazzled. The shuttle from the airport drove through a series of non-descript suburban houses and then reached a campus that had a beautiful scenery, with the creek, the hills, the old trees and so on, but ugly buildings. Around 9pm, the campus became deserted, and the whole town looked empty. Is that it?, I thought.

At the end of my talk, however, Umesh asked a really unexpected question. The day after, an AI faculty sat me down for more than half an hour because he wanted to see all the details of my extractor construction. Few people asked me where I wanted to be in five years, and I don't think I ever heard the word "vision." The last night, Umesh and Christos took me to have dinner at Cesar's. The four of us (a friend of Christos also joined) drank three bottles of wine. Clearly, something different was going on in Berkeley: the theoreticians were interested in "big questions," and knew how to have a good time; technical strength and interest in theory were widespread in the department; and bullshit was kept at a minimum.

But I came back to New York still thinking is that it? Fortunately, I followed the advice of everybody I spoke to, and moved to Berkeley.

After about a year, I started to understand what my dreamy-eyed friends were talking about, and I will miss this place very dearly if I ever move away. The fact is, I cannot explain what it is in a way that really makes sense. It's like, in Berkeley, theory is in the air, or perhaps in the espresso. People seem to work effortlessly, and to be interested in everything. Theory students study German, or Swedish, just for fun, or they sing opera, or they take film studies classes, but they also do first-rate theory work. They take a systems class because it's required, and then they publish their project in INFOCOM. Certainly, it helps that everybody around here is very talented, but this seems to be a place where it is easier to be lucky and to have good timing.

So, once more, how do students decide to come here? Probably they visit for a day, feel that it is a special place, but go back somewhat unimpressed. Someone on the faculty of their school, however, graduated from Berkeley, or was a post-doc here, or spent a sabbatical here, and he or she tells them "just go there, it's perfect for you." The students come here, graduate with excellent work, leave Berkeley with fond memories, and go on to become professors at the other top universities. And so the cycle can continue.