Poor timing and longing

Yesterday the International Film Festival featured Three Times by Taiwanese director Hou Hsiao-hsien. (His given name Hsiao-hsien is romanized as Xiaoxian in pinyin.)

There are three love stories, set in Taiwan in 1966, 1911 and 2005, and played by the same lead actor and actress. As usual in a certain recent style of Chinese film-making, the director does not have much use for such things as story and dialog.

The 1911 story, indeed, is played as a silent movie: even though the actors talk to each other, we hear no live sound, only music. Part of the dialog is reproduced in “interstitial” subtitles, that is, subtitles presented in separate frames. It is intriguing at the beginning, but it gets old very quickly. The 2005 story is completely useless. A guy goes out with a girl, who suffers from epilepsy and has a lesbian lover. That’s it, made into a half-hour section.

The 1966 story is actually beautiful. A guy meets a girl in a pool bar just before he has to leave for his military service. The two correspond by letter. On a weekend break he searches through all of Taiwan for the girl (who, meanwhile, has moved twice). He finds her when he has only a few hours left before having to go back to his base.

Contemporary Chinese filmmakers have perfected the art of telling love stories that are ill-timed (or made difficult/impossible by duties/circumstances), and of depicting the resulting feeling of longing. Just think of any movie by Wong Kar-Wai, or even of more commercial ones like Crouching Tiger Hidden Dragon or Brokeback Mountain.

Indeed, every time I see a Chinese movie like this, I am reminded that Western film-makers haven’t been able (or willing?) to take a love story seriously in a very long time. One finds romantic comedies, surely, or very dark movies about sexual attraction, usually treated as a destructive force. (I am thinking of American Beuty as a mild example, or The Piano Teacher as an extreme one.) But is there a recent Western movie about love that is not about destructive sexuality, not about being funny, and that is not an unwatchable chick-flick? To clarify the terminology: if one of the characters is dying of leukemia, it’s a chick-flick, and if one of the characters is a prostitute who looks like Julia Roberts, that’s funny.

By the way, Chen Chang, the male lead in Three Times, had supporting roles in Crouching Tiger Hidden Dragon and in 2046 and, most notably, he was also the “third guy” in Happy Together.


On rejection

It is the time of the year when those on the job market are receiving, and considering, their offers. To those who are disappointed for not receiving an offer from one of their top choices, I would like to offer the story of my first job search.

In the Fall of 1997, at the beginning of the wonderful year I spent at MIT, and still undecided whether I wanted to go back to Italy or not, I sent out a few applications for post-docs and tenure-track jobs.

By February, the rejection letters were pouring in. Some of them were written by Dogbert himself.

At one point, I received a letter from the Institute for Advanced Study. They regretted that they were not able to offer me a post-doctoral fellowship. That was quite all right, except that I had not applied for it! What was that? A preemptive rejection? Did they mean to write: “Dear dr. Trevisan, we hear that you are on the job market, and we are pleased that you did not apply here.”? What worried me was that I was going to break a record, and receive more rejections than applications, or having a negative number of job offers, as I preferred to think of it.

As it happened, in another few weeks, I received the DIMACS post-doc. In their acceptance letter, they also mentioned that they had forwarded my application to the IAS, and that the Institute would inform me at a later point of whether it was going to offer me support for a second year.

This not only explained the mysterious letter from the Institute, but also suggested that the IAS bureaucracy worked faster than DIMACS’.

Late into May, or perhaps already in June, I got a call from Columbia. Having apparently gone down their list of top candidates, back-ups and back-back-ups, they wanted to offer me a job.

I was delighted to move into my faculty housing apartment in New York (which I still miss) and to work in a very friendly department with very smart undergrads. I loved Columbia, and I loved New York. I would have stayed there until retirement if Berkeley had not made an offer that I could not refuse.

So what’s my point? There are two points, actually. One, New York is wonderful. Second, don’t take rejections too hard. In the long run, things even out. (And, yes, I know what John Maynard Keynes has to say about that, but it typically does not take that long.)

Update: Oded Goldreich has written an essay in response to this post.

The pornographic musical

New York is probably the movie-lover capital of the world, but the San Francisco film festival scene is outstanding. Counting only the major ones, every year there is an Asian Film Festival, an Independent Film Festival, the International Film Festival and the Frameline (gay and lesbian) Film Festival. In addition, there is a German Film Festival, a Jewish Film Festival, the various cycles of movies run by the PFA in Berkeley, the retrospectives at the Castro and so on. A couple of years ago, a horror film festival was introduced, called Another Hole in the Head. Clearly, the tagline of the advertising campaign was

San Francisco needed another film festival like Another Hole in the Head

(The 2006 edition is coming up, by the way.)

At these festivals I have seen a number of unforgettable movies that never received wide distribution in the US. One such movie was Tsai Ming-liang’s Goodbye Dragon Inn. Tsai Ming-liang is part of a generation of East Asian directors that have been inspired by a certain French style of movie making: through the movie, nothing really happens, except that you start to read between the lines of what the characters are saying, and to gain some insight about what they are thinking. When a resolution feels imminent, the movie ends abruptly. Tsai Ming-liang has taken this style and worked out a reductio ad absurdum. Two scenes from Goodbye Dragon Inn are seared in my memory. One scene is set in the restroom of a movie theater. There is a line of urinals, each with an ashtray next to it. A man is standing, smoking, at the urinal closest to the camera. He stands there, smokes, then puts the cigarette down on the ashtray. He keeps standing there. Other people come and go at the other urinals. He picks up the cigarette, he smokes. He puts the cigarette down, and so on. This goes on for a very, very long time. When an empty scene is kept going so long, what happens is that it becomes funny, then annoying, and finally funny again. It takes a tremendous sense of timing to make it work. (Actually, the scene is not completely empty: it is understood that some cruising is going on in the theater, and possibly, in the restroom, so one expects the scene to go off in a certain direction, but nothing happens.) Later, the cashier of the movie theater goes through the theater to pick up the trash. She wears a tutor on her knee, and so she walks with a limp, and she makes a metallic noise at each step. The theater is huge, and she goes, for ever, up and down the stair picking up the trash. The genius is that, at the end of this truly torturous scene, during which the audience alternatively groans and guffaws (a few people left), we see the cashier exiting the scene, and the scene does not end: we see the empty theater, and the noise of the limping cashier walking out of sight.

As an immediate reaction, I hated this movie. Somehow, the following day, I loved it. I tried to see other movies by him, but What time is it over there did not work for me (the scenes just felt annoying), and I was told not to even try to watch The river.

Right now, the International Film Festival is going on, and tonight’s main attraction was Tsai Ming-liang’s last movie, The wayward cloud. The movie was introduced as a pornographic musical, and that’s a fairly good description. What is the movie about? That’s obviously not the right question, but suffices to say that the premise is that Taiwan goes through a water shortage, and watermelons become the cheapest source of hydration. Indeed, watermelons figure quite prominently in the movie.

We get to see Lee Kang-sheng, the inscrutable projectionist of Goodbye Dragon Inn, shake watermelon seeds off his pubic hair, chase live crabs on a kitchen floor, sing a musical number in a dress, and repeatedly have intercourse with an overweight and accident-prone porn actress. The timing is almost always flawless and the last scene is unforgettable for the classical French style it is shot in (with the long takes and the close-ups) and the scandalous content. It goes without saying (it’s part of this style of film-making) that the movie has no dialog. Some supporting characters have lines, but nobody ever says something to which someone else replies. The main characters, of course, speak no line in the entire movie.

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.

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.