The Harvard of China

Andy is teaching an undergraduate algorithms class that combines three regular courses: the discrete math and probability course, the algorithms course, and the computability courses. (CS70, CS170 and CS172 in Berkeley-speak.) To make things more interesting, he teaches the course in English. When a foreign visitor is here, Andy always invites him or her to talk about something, anything, in the class for one 45-minutes period. (Classes are 45-minutes periods followed by 5 minutes of break.) Yesterday was my turn.

As usual, things are done in style. I meet Su Chang in her office, and she walks me downstairs, where Andy's driver is ready to drive us to the building where the lecture is. There, Su Chang walks me up to the classroom. We get there just while a military march is playing to mark the end of a period. For people who are used to hang out with celebrities, this would be no big deal, but being with a person who has an entourage is really amazing to me. Andy is there and he has just finished teaching (the class is two periods).

When another march plays in the loudspeaker, Andy introduces me to the 100-plus students "This is professor Luca Trevisan, from the University of California at Berkeley."

"Ooh" the whole class goes, when Andy says "Berkeley." This is quite unexpected: people in America hardly know that there is a university in Berkeley. But then, I realize, these are third year computer science students in the top engineering school in China. Applying to graduate school in the US must be very much on their mind, so it's no wonder that they have researched American schools and they have come across Berkeley. In any case, it is surprising that students who have Andy as a professor can be impressed by anything.

I have decided to give a lecture on zero knowledge, motivating it with a password protocol problem, and I talk about quadratic residuosity instead of graph isomorphism. The students appear to genuinely understand and enjoy the class, and the march rings the moment I finish the proof that there is a simulator.

Andy invites me for lunch, "We are going to Pizza Hut." "Oh no!" I say, before I can catch myself. Andy is unfazed by my rudeness and asks me what I would like. "Something Chinese?" I suggest assuming we would go to one of the Chinese fast food places around campus. Instead, we go to the Fancy Place of Tuesday night, where Andy orders a veritable feast.

Hoeteck is meeting a high school friend from Singapore who is in Beijing for business, and I spend the afternoon visiting the Beijing University campus. People say that Tsinghua is the MIT of China, and Beijing University is the Harvard. Famous for its Humanities department, Beijing University has a beautiful campus with a lake in the center, elegant buildings, and better-dressed students.

The evening turns more adventurous than usual, and I end up doing many new things, such as dining at a Chinese fast food place, taking the subway, seeing a working-class Beijing apartment, and joining a gathering made mostly of middle-aged Western expats parading around their young Chinese dates (I pay $5 for a Heineken; dinner for two was $4). I am not judging, because as president Bush's favorite philospher said, "Judge not etc. etc." and I, for one, don't like to be judged. But next time people tell me about post-colonialism and white privilege (we use such words a lot in San Francisco), I promise I won't roll my eyes. Berkeley's star power is put in its more proper place. "What do you do in America?" "I am a professor at Berkeley" "Bay-kay-lee?" "That's right." "Is it an egineering school?" (them fighting words!) "No" "And what are you doing here" "I am lecturing at Chin-hoo-uh" "Qinghua? WOW!".

Pseudorandomness and combinatorial constructions

At long last, today was a full day of theory. When I get to the computer science building in the morning, the security guard recognizes me, I show the badge I got yesterday, and we are all smiles.

When I go out for coffee and return, however, he stops me again to see the badge. I see I have to pay for the commotion I created yesterday. I mean, what was I going to do, go out for half an hour just for the sake of tossing the badge away and return without it?

Andy and Xiaomin take me out for lunch, and we talk about Andy's plans for his group, the teaching of theory in the department, a new honors program, funding for theory in China, and other such topics. Back to the office, they tell me about very nice new results on lower bounds for quantum local search algorithms.

Today I give a talk titled "Pseudorandomness and Combinatorial Constructions." I gave a similar talk in the Statistics department in Berkeley, and this is my work in progress for the talk I will give at ICM. Ideally, I would like to talk about some highlights of the theory of pseudorandomness in a way that is both accessible and appealing to the non-specialist. The appeal is the hard part. I have noticed a couple of things.

One is that the talk should tell a story and my angle is to tell how the probabilistic method in combinatorics and the probabilistic algorithms in computer science take advantage of randomness in settings where it's not clear that randomness should be of any use; the theory of pseudorandomness shows that, under complexity-theoretic assumptions, such use of randomness is not necessary (with some caveats in the case of the probabilistic method). This is also the organization of cs.CC/0601100

The other is that one likes to fully understand something new and clever, besides being given vague ideas about how the big picture is like. This means that it's worth spending time on something that we may ordinarily take completely for granted, but that is sort of pleasantly surprising the first time you see it. So, for example, I like to spend a lot of time explaining how one gets derandomization out of very strong pseudorandom generator. I feel that the argument really explains why the definition of pseudorandomenss is the way it is, and it is a very satisfying argument the first time one sees it.

By the way, I am not pretending that I know anything about scientific communication and I am well aware that those two points have been made over and over by lots of people. But blogger.com does not charge for postings, so there is no reason why one should feel restricted to write only about things that are interesting and/or original.

Which reminds me, I have to talk about what I did for dinner.

If yesterday's place was Fancy with a capital F, tonight's dinner hosted by Andy was off the charts. We begin with Andy's driver picking us up at the department. At the restaurant, a valet is ready to open my door, and five people are standing by the door to greet us, and two of them escort us to the elevator (the restaurant is an entire building, and we dine on the second floor). There, there is of course a person whose job is to press the second floor button, but this time she rides with us. On the second floor, three people are standing by the elevator, and two of them escort us through a corridor full of other people that seem to have no other job but to stand there. We reach our private banquet room, where we have our own two restrooms (we are a party of six). No fewer than two people are standing in the room at any given time. We each have two sets of chopstick. Oh my God, I think, this can't be good. My thoughts go back to Julia Roberts learning to use multiple forks in Pretty Woman ("start from the outermost fork and go in"). Is that how is it going to work? Outermost chopsticks for cold dishes and innermost chopsticks for the hot entrees? No. The outermost chopstick is to take food from the serving plate and put it in your plate. The innermost chopsticks are to eat. This way, chopsticks that people are eating with never touch anybody else's food. Clever.

In one outstanding faux pas, when a waitress goes around serving red wine (that is not offered to be tasted first), another waitress trails behind with an ice bucket. "Do you want ice in your wine?" For shame! Andy shoos the ice away.

The restaurant is Cantonese, from the region Su Chang is from, and she orders a number of excellent dishes, most of whom I don't know how to describe. A grouper is served in a very scenic presentation. The plate stands on a serving tray that is full of dry ice. The waitress pours warm water on the tray, making the dry ice produce a thick white smoke that envelopes the grouper.

It turns out that I ended up eating pig's intestines. I thought this would be the place where my Western squeamishness would put its foot down and declare "enough is enough, eating shrimps alive was fine but pig's intestines are good only for wrapping sausages." And so it would have happened, except that I thought it was beef, and I ate it without knowing. It tastes just like chicken.

During dinner, I score a standing invitation to visit Hong Kong. Woo hoo!

Where do you want to go?

If there are two things we don't hear enough about, they are what's the weather like in Beijing and what I had for dinner last night. On at least one of these topics, you will not find better coverage anywhere else on the internet.

My adventurous eating finally caught up with me and I woke up sick yesterday morning. It didn't last long, and I spent the day preparing today's talk and chatting with Hoeteck about what he has been up to these past months. I meet Hoeteck before lunch, and this is the first time I enter the computer science building. Officially, one needs to have a badge and show it at all times to enter the building, but nobody really does, and I was told that when I don't have the badge with me I should just stride in with confidence. I do, and a security guard chases after me shouting in Chinese. (Actually, he wasn't shouting, he was quite nice.) He doesn't speak English, but it's clear that no amount of feigning naivete will get me in. I step outside, I call Su Chang, she asks me to put the security guard on the phone, they talk, and then the security guard motions me to follow him. He takes me to another guard who asks me where I am going in English. "Theoretical computer science group" blank stare. "Andy Yao" blank stare. We get moving again, and we go to a third person. "Where do you want to go?" he asks, in better English. "Su Chang" I try this time. "Ah, Su Chang" everybody says. Which makes me wonder: did she talk on the phone to the first security guard without introducing herself? We get moving once more, but at this point I spot Hoeteck, I call him and they give me into his custody. Ironically, Hoeteck had forgotten his own badge, but apparently it doesn't matter because he doesn't look suspicious.

By dinner time, all signs of sickness having disappeared, I was ready for Su Chang's latest recommendation, a place conveniently around the corner from campus.

The place was Fancy. Allow me to explain Fancy. The place is on a second floor, but it has its own entrance at street level. At the entrance you take an elevator to go one floor up to the restaurant. A person stands by the elevator to press the second floor button for you. Upstairs, it's all dim lights, upholstered chairs, huge tables, couples on dates and business people on expense accounts. I start worrying because I don't carry my credit card around, I had only about $50 in cash, and I had to pay for two. The menu arrives and it has many entrees that are extravagantly priced even by Parisian standards (some are more than $100), but most dishes are very reasonably priced. We order a cold starter with a vegetable I don't recognize and supposedly fancy Japanese mushrooms, a dish with eggplants that tastes vaguely Italian and that is probably the most delicious eggplant dish I ever ate, a yellowtail tuna fish in a simple steamed preparation that tastes very fresh, and beef pancakes (sort of crackers that have shredded meat in their dough). Another unforgettable dinner comes out to $26 for two people, about twice what we paid at more rustic places but still no more than getting a sandwich and a perrier for lunch at Gregoire's.

Lucky me!

Here:




And there:



Notice, by the way, today's high and low temperature in the San Francisco forecasts.

p.s. The snapshots were taken at the same time: it's 9:20am Wednesday morning here and 5:20pm Tuesday afternoon in SF.

Censors with idiosyncratic taste

Perhaps you have heard of the "Great Firewall of China," the elaborate system of filtering, blocking and monitoring that tries to sanitize internet access for Chinese people.

Apparently, a large number of government officials are involved in this project, and controlling internet access has loomed largely in Chinese IT deals. If you have not already seen it in newspaper articles, see what happens if you search for "Tiananmen square" in images.google.com and then in images.google.cn. (What happened to "do no evil"?)

Access to news seems to be a primary concern, and several news sites are blocked. The choices are very interesting. The New York Times is accessible, but BBC news is not. By the way (and thanks to Hoeteck for noticing it), bbc.co.uk is accessible, it is only news.bbc.co.uk that is blocked. I think I will have to start getting my news from the BBC once I get home. Apparently, Al Jazeera was blocked at one time, but now it is not (I don't know what that means). Of course, news.chinatimes.com, the main Taiwan news site, is blocked.

A bizarre thing is that blogspot.com is blocked, but blogger.com is not. This means that I can post here, but I cannot read what I post. (That's my excuse for typoes and bad formatting.) Neither typepad.com nor livejournal.com are blocked, by the way.

If you want to know whether your favorite web site is endorsed by Chinese censors (meaning, it's blocked), just ask me.

A final note: Lance Fortnow's blog is not blocked, but Scott Aaronson's is. (Way to go Scott!)

Update 3/30/06: an astute reader points out that if I want to read Scott's blog so badly I can search for it on google, and then click on the link to the cached version of the page. Indeed, this works, but it returns Scott's blog as of March 21. If I do the same on BBC news, I get a page dated March 25. In general, for a news site, the cached version will be of little use (and contain no pictures). By the way, google news work, and it shows pictures (except that sometimes cliking on the links leads you nowhere), and even the Taiwan edition of google news is available, so it is at least possible to get the headlines of the news.

Update 4/29/06: The New York Times has an article on blocking and censorship in China. It explains that Google's dealings may not be so evil after all, and the complexity of the issue. There appears to be a major difference in the way individual dissent is treated compared to any form of organizing and mobilizing, even when very small groups are involved. It is comforting that it was probably not illegal to write this entry from within China.

More food chronicles

Meaning no disrespect to the magnificent imperial palaces, food remains the highlight of this trip, along with the discoveries of little aspects of daily life that everybody takes for granted but that are surprising to a foreigner. (And of course, in the end, theory will be the highlight of this trip, but this starts tomorrow.)

More about the little aspects of daily life some other time. Yesterday we went to a hot pot place, not unlike the Islamic Mandarin restaurant in San Francisco. The idea is that a pot with a savory soup is put on a burner on the table, and the diners cook their own morsels of meat and vegatables in the boiling soup.

Here a twist was that the hot pot was divided into two sections, one with a regular soup (which was white, for some reason, rather than clear) and one with a spicy soup, red from floating chilies and full of certain seeds that I was advised not to eat. We had thinly sliced lamb, mushrooms, sweet potatoes, spinach leaves and (non-stinky!) tofu. We mostly ate from the spicy side of the pot, and we only had beer to drink, so very large amounts of beer were consumed. Part of it was someone's effort to get someone else drunk (the efforts badly backfired).

It's becoming repetitious to point out how cheap it is to get good food here, but it's really hard to get used to it. The meal and the beers were US$16 for three people. (Or, in other units of measure, about 5 espressos, or 120 small lamb skewers.)

stinky tofu and drunken shrimps

This morning, before leaving, I check the weather forecasts at Yahoo! Weather.




Yes, the weather forecast is "dust". There are sandy deserts not far from Beijing, and when the weather is very windy the dust blows into the city.

We begin with a visit to the Summer Palace. It is an enormous residence built near a lake. The weather is so cold and windy that it is hard to enjoy it.

For lunch, we tell the guide that we appreciated that yesterday we went to a much better place than the touristy place of Saturday, but that we would like a meal not catered to Western taste at all. (Yesterday's place still had a bit of American Chinese restaurant taste.) We got what we wished for. The first dish was pork served with some vegetables that had been dried and then re-hydrated. The cut of pork was probably the one used for bacon: half of it was fat, but it was cooked in a way that was eatable. Next course was stinky tofu, a dish that has a reputation for being, to put it mildly, an acquired taste. The guide and the driver were eating with us, so there was no wimping out of it. To me, it tastes rotten, in the literal sense of eating something that has gone bad, but I can imagine how sharp cheese tastes to someone who has never eaten it. I am sure I will give stinky tofu another try, but not too soon. Finally, the highlight of the meal were the drunken shrimps. They were served in a bowl that looked boiling hot. It turns out, instead, that it is a cold dish. The shrimps are put alive in a marinade that is made mostly of alchool. When the dish is served, the shrimps are still alive and kicking (this is what I mistaked as boiling). After a while, when the kicking has almost stopped, you pick up a shrimp with the chopsticks, by the head, and put most of the body in the mouth. You chew, and then you spit out the pieces of shells that you did not chew. Again, I did not feel like wimping, and down went the really fresh shrimps. They actually tasted quite good.

The restaurant was ridicolously overstaffed. Eight people were milling by the door to greet us when we arrived. At least two people were near our table at any time.

We continue with a visit to a Hu Tong, an old style neighborhood with small alleys and old houses. Most Hu Tong were torn down for new developments, but finally the government realized that they had cultural and touristic value. The tour was embarassing, at least to me. We went around in a rickshaw, with a person pedaling to tow it, a means of transportation that I find ethically questionable and, more importantly, I felt as dignified in the rickshaw as I would be in a horse carriage in Central Park. It really says "silly Western tourist." (Of course, in Central Park, it says "silly Japanese tourist"). As part of the tour, we walked into somebody's house, and they offered us tea and sat down for a while. Again, the notion that somebody's house would be a tourist attraction because "it's so exotic" bothered me to no end.

Many of the houses have been converted to bars and to souvenir shops, selling Mao's red books, posters of the cultural revolution, but also posters of Che Guevara and the like. It is clearly only a matter of time before we see stores selling t-shirts that read "my grandson went to Beijing and all I got is this lousy t-shirt".

Update 4/3/2006: Pictures

The cherry trees are in blossom



and some of them are amazing



This is how the Hu Tong looks from above

the soldier and the fire extinguisher

Today, with a different, and more friendly, tour guide and the same driver, we begin the day with a visit to the Temple of Heaven, the place where the emperors used to sacrifice animals to the Gods. The place now doubles as a public park, and on a sunny Sunday it was full of people exercising, playing cards, playing music and so on.

After a decent lunch, we moved to Tien An Men square to go see the Forbidden City, the imperial compound. Walking around the square, one notices a number of podiums (podii?) on which soldiers stand on guard, and each has a fire extinguisher next to him. What does a soldier need a fire extinguisher for, I ask the guide, in a square that is all concrete? Well, he starts explaining, quite flustered, there is this religion called Falun Gong...

So, what do you do when people, driven to desperation by their oppression, put themselves on fire in a public square? Well, you give fire extinguishers to the soldiers... Clearly, the problem is with the fire.

The square itself gives me the shivers, because the massacre that happened there was perhaps the international event that shocked me the most in my life. The students who died were about my age, and we all had a lot of simpathy for their movement in Italy. Maybe one day there will be a monument honoring the dead students in the square, just like now in Rome there is a monument to Giordano Bruno in Campo de Fiori, the square where heretics like him used to be executed.

The forbidden city combines an enormous scale with a sense of simplicity and good taste that is not seen in European royal palaces.

We later moved on to a museum of modern art, with unremarkable contemporary Chinese painting.

Dinner was soup of mushrooms with pork, a rabbit dish, and pancakes with bean curds, US$9 for two people.

Update 4/3/2006: Pictures

This gentleman is having a jolly time singing with his buddies in the Temple of Heaven



The guy with the cap is playing an instrument that has a single chord.



The soldier and the fire extinguisher



Yes, the red sign is for Kentucky Fried Chicken.

the emperor and the scholars

Yesterday we started off at 10am (more like 10:05, to the chagrin of the tour guide) to see the Sacred Way and the Great Wall. For a group of four (professor N., myself, Hoeteck and guest), we had our own driver, minivan, and two tourist guides.

The highway we drove on has several pedestrian bridges. At one point we saw a flock of sheeps descending the stairs of one of these overpasses.

The Sacred Way is a sort of cerimonial road leading to the tombs of Ming emperors. The main attraction at the beginning is a series of statues, that guard and protect the dead emperors. There are first twelve animals, some real and some mythological; each animal comes in two pairs, one pair standing and one pair sitting. Then there are six pairs of people. Three are warriors and three are scholars. Yes, the scholars are right there with the warriors, the lions, and the mythological animals when it comes to keep the emperor company. The warriors are depicted with their armor and sword, while the scholars are seen holding a tablet with some notes that they are going to read to the emperor.

After appreciating the Ming attitude towards scholarship, we had a terrible lunch and proceeded to the Great Wall. That section of the wall appeared to have been almost completely reconstructed recently. The wall went up steeply along the side of a hill, and the main attraction is simply to go up all the way until the peak of the hill, from where there is a broad view of the valley and one can see the wall snake around for miles.

On the way back, we drove through side roads, probably to avoid traffic, and we had a glimpse of working-class China which was actually one of the highlights of the day for me. At one point the driver stopped, and he explained that he was going to buy some fish to take home in a place that he knew. Intrigued, we followed him (it was 5pm and we had had a disappointing lunch) in a place that looked quite unsanitary. He got this box with several small fishes that had been deep-fried and then marinated for several hours to become so tender that one could eat the whole fish. He offered it and I was the only one to try it. It was really good, except that I did not eat the head and the tail. Then everybody wanted to try it so we got another box. At this point even the tour guides bought a box for themselves. And there went my resolution to be careful with the food.

The dinner was in a muslim-mandarin place recommended by Su Chang, Andy Yao's very efficient secretary. Dinner for 3 with delicious lamb skewers, beef stew, a spicy chicken dish and bok choi with mushrooms was less than US$18, or $6 per person. (It would have been around $23 total, but they gave us a discount because when we got there they told us that the wait would be ten minutes but we actually waited for 40 minutes.) The large lamb skewers were about 70 cents each. We can't remember the price of the small ones, but it was either 25 cents or 12.5 cents.

This really puts things in perspective. An espresso here costs about US$3, which is steep by US standards, but is ludicrous when you realize how many lamb skewers it costs.

Finally, back to the same club of Friday, where I realized what difference (for the better) it makes if one is awake there. The locals are friendlier to Westerners than I thought. Communication, however, is sometimes problematic. Sample conversation: "Where are you from?", "Italy," "oh, that's a beautiful city." Some locals, on the other hand, speak excellent English and are quite sophisticated in their knowledge of Western culture. Another version of the "Where are you from?", "Italy" conversation, indeed, proceeded with the guy talking about De Sica (for the Italians reading this, he meant Vittorio, not Christian) and how much he liked Bicycle Thiefs.

Update 3/27/2006: two days after eating the fish, still no adverse consequence. And, in my one-man protest against the high price of espresso, this is my third day without coffee.

Update 4/3/2006: Pictures of the great wall

It's steep to go up



But then there is a view

Don't come to the podium!

Flying for twelve hours in a packed plane, with the seat of the person in front of me crushing my knees and the toddler in the seat behind me kicking my back has become the norm of my trips to Italy. (And this only gets me to Amsterdam or Munich, from which another packed flight has to be taken to make it to Rome.)

For my twelve hours trip to Beijing I was hoping that at least the plane would not be full. When I reach the gate, a person is giving orders in the loudspeaker: "if you want to change your seat, don't come to the podium: the flight is full and we cannot do any seat change." Poor me, I think, and then she adds, for good measure: If you do not have a seat, then do not come to the podium either, wait for us to call your name."

Oh well, I think, I cried because I had no shoes... and while I am lost in such consoling thoughts my name is called. I show the person my boarding pass, "see I have a seat already," she tears my boarding pass to pieces and then ... she hands me a differently colored boarding pass. "We moved you to a business class seat."

And not just that, an exit row business class seat, an aisle, exit row business class seat. So much space all around me, my eyes can barely take it all in.

And off we go with a glass of champagne. For lunch, an appetizer of smoked salmon and grilled portobello mushrooms and a filet mignon wrapped in bacon. And all around me, United flight attendants who smile. You have got to see it to believe it.

In Beijing, a driver is at the airport to pick me up and to drive me to campus. He speaks no English, but this is no problem. His driving style is unique. He has the smoothness of the American limo driver, avoiding sudden acceleration and decelerations, and at the same time he drives like an Italian, continuously changing lanes, driving for a while on the emergency lane, cutting in front of cars, squeezing between two other cars by imagining that there is a lane in between, almost running over pedestrians and bikes, and so on. (And all at constant speed!)

The accomodation is unbelievable. A three bedroom/two bathroom apartment with hardwood floors, a giant flat-screen tv in the living room, a walk-in closet in the master bedroom, and a shower cabin in the second bathroom that is about the size of a New York hotel room. A staff of four mans the front desk. Currently there are two guests, professor N. and I. Soon it will be just me. The staff is very excited to see me and to have something to do.

A delicious dinner of cold salad of potatoes and mushrooms, spicy whole braised fish, and hot pot with potatoes and frogs follows, and then drinks at a bar where I am the only one who does not score a phone number. Thus ends my day of being treated famously.

Update 4/3/06: Pictures of the Tsinghua visiting faculty residence.

The living room with the large screen, flat panel, tv.



The well-equipped kitchen



The dining room seats six



The study



The guest bedroom



The master bedroom



The shower cabin that can fit a small crowd

The bridge-and-tunnel coyote

A coyote was found in Central Park today, who had apparently reached the city from Westchester County by using a train bridge. As mayor Michael Bloomberg points out: "This is New York, and I would suggest the coyote may have more problems than the rest of us."

Indeed: they are taking him from Central Park to upstate New York!