Sunday, April 30, 2006

The truth is in the gut

If you haven't seen it already, Stephen Colbert's remarks at the White House correspondents dinner can be found here (part 1) and here (part 2).

A transcript is also available.

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.

Wednesday, April 26, 2006

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.

Monday, April 24, 2006

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.

Friday, April 21, 2006

The \$325,000 washer-dryer

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.

Thursday, April 20, 2006

Welcome, Yonatan

You are a lucky kid.

Tuesday, April 18, 2006

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 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.

Sunday, April 16, 2006

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.

Saturday, April 15, 2006

What is it with the R. Cohens and journalism?

This idiotic article by Richard Cohen in the Washington Post was the recipient of much, well deserved, abuse when it was published.

But now we have Roger Cohen stringing together tired and poorly timed cliches and making them into an article for the newspaper of record.

Is there a Robert Cohen, somewhere, who, right now, is plotting a trite article for the New Yorker?

Friday, April 14, 2006

Sometimes evil is dumber

In Spaceballs, Rick Moranis has one the best lines ever:
Evil will always triumph because good is dumb.

There is hardly any major political event that cannot be explained by this rule. The recent Italian elections are an exception, if you follow my triple negation.

Berlusconi has been notorious for making the Italian parliament pass laws specifically designed for his own personal interests. I will not give too many examples, because the Italian readers know all about it, and the other readers have no reason to care. Suffices to say that at least one of Berlusconi's TV station operated illegally for a long time (using broadcast frequencies that the law did not allow it to use), and at least twice it was shut down by court order. The court orders were followed by executive orders, and then laws, allowing it to broadcast. The use of the frequencies would have been worth billions of dollars if it had been auctioned. Berlusconi has been under trial for several alleged felonies, most notoriously for accounting fraud and for bribing a judge. In all cases, his strategy was not to defend against the charges, but to delay the trials until the statute of limitation would make the cases disappear. In one infamous episode, he had a law passed that decreased prison terms for accounting fraud so that the statute of limitation would apply earlier to a trial that was almost over.

Given this attitude, it is not surprising that various changes were made to the electoral law, in hopes that they would benefit the right-wing coalition. One change was to allow Italians living abroad to vote and elect their own members of the parliament. The convential wisdom was that Italian expats would be very conservative. The other move was to change the apportionment system for the House, so that the coalition receiving a plurality of the vote would get at least 55% of the seats, regardless of the actual number of votes. (This was done under the theory that the right-wing coalition would win by a small margin.)

In the last elections, however, the left-wing coalition won the House by a margin of 0.1%: 49.8% versus 49.7%, and it got 348 of the 600 seats. In the Senate, the right-wing coalition won a majority of the votes in Italy, and one more seat. The expat vote, however, gave 4 out of 6 seats to the left-wing coalition, tilting the Senate majority in its favor.

Tuesday, April 11, 2006

The boiling of babies shall commence tomorrow

After a full day of contradictory news, the final results of the Italian elections are in: there were enough coglioni to vote Berlusconi out of office if only by a tiny margin. Never a member of the reality-based community, Berlusconi, before the elections, warned that his opponents are communists, and, in China, communists boil babies. Now I look back with suspicion at all those delicious dinners.

Goodbye to Mirko "poor Europe, the faggots are in the majority" Tremaglia, minister for Italians abroad, to Mario "we'll bring pigs to piss on the ground where mosques are going to be built" Borghezio, member of the European committee for civil liberties, to Rocco "the family exists in order to allow women to have children and to have the protection of a male who takes care of them" Buttiglione, minister of EU policies, to Marcello "same-sex marriage is a whim, not a civil right" Pera, speaker of the Senate, and to all the gang. Please exit slowly and let the door hit you on the way out.

What a long, dark, night of the reason it was, and how many monsters it has created!

And, Fausto Bertinotti, I know you are reading this, please, please, I am begging you, don't fuck it up this time.

Saturday, April 08, 2006

Feminism for dummies

One of my favorite readings on the web is Bitch, PhD.

She talks about being a woman in academia, about child rearing and about feminism in terms that are very concrete and understandable. This post where she explains feminism to her five years old is something that even I can follow.

I wonder if she writes pseudonymously because, in gender studies circles, it would be shameful to write so clearly.

By the way, since she writes pseudonymously, we don't even really know that she is a woman. It would be really interesting if Bitch, PhD, is written by a man who switches all genders when he talks about his life experiences. So he is a professor with a stay-at-home wife who gave up her career so he could move to his university of choice. And he has a mistress in a nearby city: his wife knows and she does not object. Suddenly, a radical and cool lifestyle becomes suspect and objectionable, even though it is, of course, the same lifestyle (only the genders of the involved people have changed).

Which makes me wonder: has liberal and feminist thought come up with its own double standards? (I have my own answer, but I wonder what you think.)

On a somewhat related note: has feminism made flirting less fun?

Beware of the tomato-wielding terrorists

The car of the US ambassador in Caracas was pelted with eggs and tomatoes yesterday. Venezuela's ambassador was summoned at the White House and was warned of "severe consequences" if such an incident were to happen again.

U.S. Embassy spokesman Brian Penn tells the Associated Press this harrowing tale:
We were under attack by these motorcyclists throwing fruits and vegetables.

Update: as of April 10, the text of the AP article has changed, and the hilarious Brian Penn quote is not there any more. I wish I had saved a copy of the April 8 text.

Friday, April 07, 2006

The Tao of Berkeley

Whenever I saw a prominent inscription in a palace within the Forbidden City, I would ask the guide for its meaning. One inscription was 為無, which, read right-to-left, is wu wei in Pinyin, or 无为 in simplified characters. The tourist guide gives a long, and fascinating, explanation. More or less, wu wei means "not doing," or "inaction." The character 无, wu means "not having something" and 为, wei, means, among other things, "to act." In this context, wu wei is a principle of Taoism, and it means something like "letting things take their course." The emperor who put that inscription in his room wanted to be reminded not to be a tyrant, not to unduly impose his authority. A famous maxim of Taoism is wei wu wei 为无为, that liberally translates into "getting things done by doing nothing."

Wow, I realize, Umesh is a Taoist!

Ever since coming to Berkeley, I have tried to practice wei wu wei, without knowing that it had a name and that it was a centuries-old concept. It is not so easy. After six years, I have gotten pretty good at the "doing nothing" part, but anybody who has ever sent me a paper to referee knows that I am still struggling with the "getting things done" part.

I like Chinese calligraphic art a lot, and so I definitely wanted to find a calligrapy of wu wei and put it in my office as an inspirational poster of sorts. Unfortunately, it was one more thing that I did not have time for.

Thursday, April 06, 2006

The Trojan pandas

You probably know about the history of Taiwan. When the Kuomintang lost the civil war against the Communists, more than a million people fled to Taiwan and created their own independent state. After a long period of one-party rule, Taiwan is now a democracy, and a fairly liberal one at that. In 2003, Taipei hosted the first gay pride celebration in a majority-Chinese country, and the Taipei mayor took part in it. Taipei is also considered one of the capitals of Chinese food, and you'll read all about it on this page next month.

This is all wonderful, except for the "independent state" part, a matter of fact that is not recognized by China, which considers Taiwan a "renegade province." The efforts of the PRC to negate, in every possible symbolic way, the independence of Taiwan are legendary. If you live in a big city pretty much anywhere in the word, and you search your phone book for "Taiwan consulate," you will not find it. That is because in order for a country to have diplomatic relations with China, they must not recognize Taiwan as an independent country. Instead, Taiwan has Taipei Economic and Cultural Offices that provide consular services under the name of a trade and cultural office. This is the one in San Francisco.

Arriving in China, you have to fill up a form to be given to the customs officer. It has a box to check if you are a Chinese national, and another if you are a foreigner. If you are a foreigner, there is space to write your nationality; if you are Chinese, there are a few more boxes to specify if you are from one of three "special" provinces: Hong Kong, Macao and Taiwan. (Note the double symbolism here.)

At the airport, flights to Taiwan leave from the international terminal, and, obviously, we can't have that. So all signs refer to the international terminal as the "International/HK/Macao/Taiwan" terminal. By the way, in the US, flights to Canada leave from the domestic terminal.

Did you hear the story of the Trojan pandas, by the way? As part of a recent series of initiatives targeted at the Taiwanese public, China wanted to donate two pandas to Taiwan. The catch was that the pandas would be sent to Taiwan under the law that regulates domestic transfers of pandas. Taiwanese authorities rejected the deal, and called the animals "trojan pandas." Wonkette makes the obvious 5th grade joke.

I wish I had found Chungking Express

In Beijing, I bought a DVD of Crash for 75 cents from a street vendor.

I was advised not to buy movies off the street, because they would be likely to be very bad pirated copies, shot by some guy with a video camera in the movie theater, like in the famous Seinfeld episode. Indeed, this only made me more eager to buy DVDs from street vendors. So what if the video quality is bad and you hear other people's voices: just to be able to tell the story of that one time I bought a movie in Beijing and it turned out to be shot illegally in a movie theater, I am more than willing to spend 75 cents.

The movie, however, is an original copy, or perhaps an illegal copy of an original one. It has all the extra features, the subtitles are available in English, Chinese traditional, Chinese simplified, and Spanish, and so on.

Even in legitimate stores, DVDs rarely cost more than $4. I had a long list of movies I wanted to buy, but that I could not find in the short time I had to look for them. One more reason to regret the shortness of this trip.

Tuesday, April 04, 2006

The things I notice

Scott summarizes in thirteen words what I have been writing so far
Luca is filing travel reports from Beijing, where apparently the food is excellent.

Where were his powers of synthesis when he was writing his thesis?

Is there anything else to write about China except the food? Surely there is. What about the shortage of unskilled labor? Is the increased funding of higher education and research a preparation to a future when more skilled, and better paying, jobs will move to China? If so what can we do to keep these jobs in America? What's going on in the West of China, with peasants rioting in the countryside against developers grabbing land with the help of corrupt politicians? How are people dealing with privatized health care? What will the consequences be of an increasingly independent judiciary? And, most importantly, what's up with the Chinese patriarchy in these post-colonial times?

These are all good questions, but I'd rather talk about cell phones and security guards.

A typical undergrad gets about \$60 a month from his/her parents as an allowance (the university provides room and board but the \$60 must suffice for clothes, entertainment, dining out and so on). A typical salary of a recent college graduate is in the range of \$200 to \$400 a month. Some jobs in the private sector, or in profitable state companies run like private ones, pay much more, but they are relatively rare. Even so, everybody, even the undergrads who subsist on \$60 a month, has a cell phone. While making calls is comparably expensive, text messaging is very cheap. So, everywhere, you see people typing messages in their phones, while they wait for the bus, while they walk, in clubs, in restaurants, while they are talking to you. (How do you type in Chinese using a 10-keys keyboard? I'll let you guess.) Hoeteck procured a local phone for me, and so I too could be seen walking around typing into the phone like a local. A cute note is the use of '88' as an abbreviation for 'good-bye'. That's because the word for 'eight', 八 ('ba' in Pinyin), is pronounced 'pah' with a high-pitched tone, and 'pah-pah' and 'bye-bye' are close enough. The wonderful thing is that, in a place where everyone has a phone, it never happens that, at a very bad time, you hear a ring and then someone says loudly "Hello. No, it's not a bad time at all."

The Chinese have a thing for uniforms. In every shopping mall, in every parking lot, most everywhere, somebody is standing in a military-looking uniform, even if he is just the security guard or the valet parking attendant. Tsinghua is an exception: the security guards wear dark suits and go more for a secret-service vibe. All these people, and, even more so, the real soldiers, have a small built, and, especially, they have really thin waists, that are emphasized by tight belts worn outside their coat. As Hoeteck noticed, they also all look the same, with fine features and very narrow eyes. The look seems to get more extreme the more important is the place they are guarding. The soldiers at Tiananmen square hardly had any eyes or any waist at all. Even the Tsinghua guards have this uniform look, and the day I was sent from one security guard to the other, all dressed in dark suits and looking the same, it felt like the scene in the Matrix will all the clones of Hugo Weaving. To me, these guys look adorable, but this must be a matter of cultural dissonance, it cannot possibly be the vibe that their employers want to give. I have wondered if this look might actually read as menacing to the locals: maybe the narrow eyes are read as aggressive, and being thin is read as being fit. More likely, these guys are just seen as elegant in their uniforms, and the purpose of a security guard is not to protect a building, but to decorate it. If you break the rules, the subtext may be, you are going to be in such big troubles that whether the security guard will hurt you or not will be the last of your preoccupations. In any case, I am sure even the smallest of those guys is trained to kick ass if the need arises. And I cannot shake the suspicion that they always also have, out of sight, a bunch of huge ugly guys that will come out if trouble starts.

Monday, April 03, 2006

P, NP, and Mathematics

Avi Wigderson has just posted the paper based on his forthcoming ICM plenary lecture.

I suggest you stop doing whatever you are doing (I mean, come on, you are reading a blog, you can't be too busy...) and read it now.

In August, Avi will bring the lieta novella of the P versus NP question (and of complexity theory in general) to, literally, thousands of mathematicians: ICM 2002 in Beijing was attended by more than 4,000 people, and many of them went for the conference not just for the food.

This will be an important turning point on how other mathematicians look at what we do. Even now, of the latest generation of pure mathematicians, those who like problem-solving more than theory-building (and who naturally gravitate around analysis, combinatorics, analytic number theory and probability) can be very sophisticated in their appreciation of complexity, and, I think, they see it as one of those parts of pure mathematics that one should know something about, even if one does not work on it.

When Terence Tao (analyst, number theorist, and combinatorialist of "primes in arithmetic progression" fame and likely 2006 Fields Medalist) visited Berkeley, we talked for some time and he asked a few questions. "When you have a subset of the hypercube whose Fourier spectrum is concentrated on a few Fourier coefficients, is there a way to find them without looking at the whole hypercube," yes, it's the Goldreich-Levin theorem (he wanted to see the proof, we went through it in about five minutes); "if P!=NP, would this settle the question of whether there are problems that are hard on average?" It's unlikely; "is it plausible to use Fourier analytic techniques to study the circuit complexity of functions?" not for general circuits, because of Razborov-Rudich (he had heard of it before, and he wanted to know what exactly is the statement of Razborov-Rudich).

If you have enough time to read my Beijing restaurant reviews, you also have enough time to read this article by 1998 Field Medalist Tim Gowers titled "on the importance of mathematics." The P versus NP question figures quite prominently. Since you are at it, you may try to find the video of his talk at the Clay Institute web site (the link from Gowers' page is broken) [Update the talk is available at] on the same topic. And, I don't mean to boss you around, but you should also buy and read this book, a masterpiece of mathematical exposition for the general public. (Circuit complexity and NP-completeness are featured.)

The next New York Times bestseller

Despite all the things I have eaten, and faithfully documented, I have lost two pounds. What the hell? Soon you'll read all about it in my upcoming book The Beijing Diet, the asian male response to French Women Don't Get Fat.

In Theory: now with pictures

You can now see pictures of the visiting faculty apartments at Tsinghua, of the Great Wall and of the soldier with the fire extinguisher on Tiananmen square.

Sunday, April 02, 2006

A party I had to miss

Near the Hu Tong neighborhood we saw the advertisement for this party:

Hoeteck cleverly commented that the concept of the party is probably that you go there and nobody shows up.

This is a public service announcement

If you are reading this, chances are that you are a theoretician. And if you are a theoretician, chances are that at some point Andy will invite you to Beijing. If he does, then obviously you will accept, and your number one question will be: where are all those restaurants that Luca has been talking about?

Ask no more. Hoeteck has compiled a list of the places I have been to. For each place, the name is spelled in the Pinyin romanization (without accents) and in Chinese characters. (In "simplified" characters, as currently used in mainland China.)

Friday, March 24

name of restaurant: gan guo ju 干锅居
location: near Tsinghua University east gate

This is where we had an awesome whole fish as well as a delicious frog dish. (It was my first time eating frogs.) More here.

Saturday, March 25

name of restaurant: xin jiang ban shi chu yi si lan fan zhuang 新疆办事处伊斯兰饭庄
location: "Xinjiang office" in northwest Beijing

This is the islamic Chinese restaurant with the lamb skewers costing 25 cents. More here. Unfortunately we have no idea how to find the marinated fish place again.

Sunday, March 26

name of restuarant: jiu tou niao 九头鸟
location: near Beijing University south gate

This was incredibly cheap and still quite good. It is within walking distance from Tsinghua, and the walk is pleasant. (See here)

Monday, March 27

name of restaurant: kou fu ju 口福居
location: da yun cun (大运村), near zhi cun lu subway station

This is the hot pot place.

Tuesday, March 28

name of restaurant: zui ai 醉爱
location: beside lotus center, near Tsinghua University east gate

This is the Fancy Place with the elevator attendant where we ate for $12.5 per person. The eggplants and the yellowtail tuna were amazing.

Wednesday, March 29

name of restaurant: li chang 黎昌
location: off Beijing University west gate, on the way towards the
summer palace

The place with the private banquet room with our own two bathrooms.

Friday, March 31

name of restaurant: xin kai yuan 新开元
location: off Beijing University

Andy's favorite place in Beijing.

name of restaurant: qiao jiang nan 俏江南
location: wang fu jing shopping district (multiple locations)

Very good, but the other branches are likely to be less expensive.

Saturday, April 01, 2006

Home, queer home

This afternoon I am out with my \$13 jacket (not the one that looks like a sport jacket and that is hard to pull off) and we run into our most upper-class gay friends, taking a walk with their child. "Luca, you always look so fashionable" one of them approves. Woo hoo! It passes the queer eye test.

Andalu has a 45 minutes wait for dinner, and we stroll through the Mission used books stores. In one bookstore, the owner is telling a customer about alchemy, immortality, and aliens. There are two, competing, races of aliens, I overhear. The lizard-like ones are indigenous to Mars, and it was their Luciferous experiments that turned the planet into what it is now. Then they moved to Earth, to Atlantis, and we know how that ended. George W. Bush, unsurprisingly, is a lizard-like alien himself. Another bookstore has a shelf devoted to China. I pick up a book at random: "Gender and Change in Hong Kong: Globalization, Post Colonialism, and Chinese Patriarchy". It's available from Amazon if you are interested. How much I love this city!

Dinner at Andalu is \$82 for two people, welcome back home, Luca.

They need your conserve

If you know someone who has been to China, you have heard the stories about the signs written in English. Chinese is, of course, a language whose grammar is very different from that of Indo-European languages. Even thinking in terms of "verbs," "adjectives," "nouns," and so on is not very apt. There are words that have very broad meanings, and when you string them together it becomes clear which one describes the action and which ones describe the actor. If you translate word for word into English, the effect is surreal.

Here are some of my favorites.

On the Sacred Road:

On the Great Wall (there are lots of them):

In the gardens of the Forbidden City there are several rocks that are naturally carved by erosion and that are extremely beautiful. (They are not indigenous to the place, they were brought there at great expense.) This is the biggest, it's about 30 feet tall:

And this is the sign next to the rock:

And this is the name of one of the buildings in the Summer Palace:

Finally, this sign is next to the restrooms in the clock tower near a Hu Tong neighborhood:

My suggestion is to hold it until you can find at least a four star one.

More pictures will be added as updates to old posts.

All good things have got to end

Before the talk on Friday, Andy took us out for lunch at his favorite place in Beijing. We had again a private room and an endless stream of dishes. I was shamed into eating kidney, and there goes another food taboo. As always, the whole fish dish was my favorite.

On our way out, I notice that other people are having lunch in semi-private rooms, that are closed on three sides and then have a sort of carved wood screen to partially close the fourth side. Poor people, I find myself thinking, having lunch on a weekday in a place where other customers can see them. How can they live like this? I am in for a rude awakening when I am back in San Francisco.

In the afternoon, Hoeteck and a friend take me to go shopping. I really like the way several guys dress in Beijing; it's a style that I can't quite describe, sort of Urban Outfitter but without trying so hard to be cool. Something that I really like are those jackets that are cut in the shape of a three-button sports jacket, but more roughly, without shoulder pads and cuts in the back. They fit tightly and they are worn over jeans and light sweaters, as if they were a coat. I have seen them sold for about \$18 near the university, but I did not know how to ask for size and color.

We go to a department store two floors of which are divided into lots and lots of small cubicles, each cubicle being independently operated by one or two people. I see something I like in one cubicle, try it on, and Hoeteck's friend takes it from there "If you want it, I can get it for \$12.5" he says in English, and then the bargaining starts in Chinese. The owner wants about \$50, we start at \$10. We walk out on our final offer of \$12.5, while the owner is down to \$15. She actually agrees to \$12.5 when we are already out of the place, but we decide to see some more. The scene plays itself out a few more time, and it is a lot of fun. I end up buying two jackets for \$13 and \$15. It turns out that one has to be really thin to pull these jackets off, and even I don't quite have the right body type, but at these prizes I'll give them a try. (One of them is the 3-buttons style, the other is a more conventional Spring jacket.)

On a different floor, there are stores of what must be local brand names. One sign says "No Sale" in English (what? I wonder) and, more accurately, "No Bargaining" in Chinese.

I remember that, when I was a child, it was common in Italy to bargain at locally owned shops. Even now, some pleading can take 10% off. But, at the time, this was so common that department stores had similar signs that read "Prezzi fissi." (Fixed prizes, meaning no bargaining.)

For dinner (I am sure you wanted to know) we want to go to a Shezuan place that Hoeteck knows. It is a small chain and it has a branch not far from where we are. It turns out that it is in a fancy shopping mall, the one with the Burberry store, the Ermenegildo Zegna store, and so on. The restaurant is full of Westerners, they have a menu in English, and they add a 10% service charge. These are not good signs, and dinner for three is \$60, at least 50% more than it would have been at the other branch Hoeteck had been to. The food is good as usual, and the whole fish is, as usual excellent. For dessert we have green tofu. It is serverd boiling hot (and liquid) in a terrine when we are midway through the dinner. After it cools down, it becomes solid, or about the consistency of a flan.

Finally, once more to the usual club, where the night plays like a repeat of last Saturday, and so the whole week comes full circle. This morning, off to San Francisco, way too soon.

No time for Gowers Uniformity

On Friday I give my second research talk, this time about the PCP results in this work done with Alex Samorodnitsky. This is the stuff that I have been most excited about in a long time. To analyse a certain PCP construction, it turns out that the ideal anlytic tool is the "Gowers uniformity" of a finite function. Gowers uniformity is a sort of measure of pseudorandomness, and there is a precise technical sense in which the use of this tool can be seen as "generalized Fourier analysis."

Gowers introduced this notion (obviously, he just called it "uniformity") to give an analytic proof of Szemeredi's Theorem on arithmetic progressions (not to be confused with Szemeredi's Regularity Lemma, which was developed as part of the proof of the Theorem). Previously, an analytic proof (with good quantitative bounds) based on Fourier analysis was known for the case of progressions of length 3, and for the general case the only known proofs were Szemeredi's one (that used the regularity Lemma and hence had a terrible quantitative form) and Furstenberg's proof based on ergodic theorey (that uses the axiom of choice and has no quantitative form at all). There is a very clear technical difficulty in using a Fourier-analytic approach for the case of longer sequences, and Gowers approach breaks very elegantly through it.

It is intiguing that the Fourier analytic expressions that one gets in the length-3 case of Szemeredi's theorem are similar to the expressions that one gets in the study of linearity testing and PCPs, and that the technical difficulty for progressions of length 4 is similar to a bottleneck that one encounters in defining PCPs that are very query-efficient.

So, perhaps it is not surprising that this notion has been useful in our analysis. In any case, Fourier analysis over finite Abelian groups is used in several other places in computer science, notably in learning and in circuit lower bounds, and I think it is likely that a technique that has "gone beyong Fourier analysis" in two such unrelated areas as additive combinatorics and PCP can find further powerful applications.

Unfortunately, I did not have time to tell this part of the story on Friday, as I wanted to spend some time explaining the PCP model and motivating the linearity testing and "influence testing" problems that we study.