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.

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.

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

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 and then in (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), is accessible, it is only 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,, the main Taiwan news site, is blocked.

A bizarre thing is that is blocked, but 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 nor 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.