Talk talk China

If state’s support and Andy’s energy do not wane, Andy Yao’s institute in Beijing might become, over time, the next Weizmann: one of the best places for theory in the world, the first choice for Chinese nationals who complete their PhD in the US, and an attractive destination for non-Chinese for their post-doc/ sabbatical/ summer. Meanwhile, it is an exciting place to be, with a palpable sense that great things are going to happen. (And I don’t remember if I have already mentioned that the food is good.)

As I anticipate many happy returns, I have been reading a bit about China, and I have enjoyed reading talk talk China. It is written by three expats, living in Beijing, China and Hong Kong. Some entries were written when one of them lived in Shanghai. It is mostly devoted to ranting about China, so many posts may be offensive to many people, but, through the ranting, they say very interesting things about China, about foreigners in China, and about the Chinese.

Their claim to fame is this post about the “lao wai death stare,” which I experienced even in my very short stay. This , this, this, and this sound familiar too.

Apparently, it is very difficult for a foreigner, or even for a Chinese-born white person, to feel accepted. The comments on that post are particularly interesting, because many posters make a comparison with Taiwan and speculate on how things may change in China. (Or, in the rest of China, if you prefer.)

Indeed, when I arrived at the customs/immigration at Beijing airport, I felt something was strange with the signs pointing to the lines for “Chinese nationals” and for “Foreigners,” and then I realized I had never seen the word “foreigner” anywhere else in this context. In Europe it’s always “EU Nationals” and “Non-EU Nationals,” in the US it is “US Citizens” and “Visitors” (even though, in the paperwork, I am an alien, which is about the worst term they could possibly choose) and so on. My impression is that a lot of this has to do with there being no notion of “politically correct speech” in China (yet). “I like foreigners, with their big noses and sunken eyes” someone told me in Beijing, presumably as a compliment. I am not saying it is a bad thing, I am not a big fan of PC-speech myself. (But this is a subject that would need its own post.)

I had the most fun reading this post about English names. (Warning: even the title of the post is offensive.) In Beijing I met a Beckham and a Gerrard (they are names of football players), and in Taipei I met a Bevis, but this is nothing compared to the examples given by the original poster and the commenters. Of course, now that I am considering “reckless card” as my Chinese name, the joke is on me.


Hair, addresses, lockers and beer

A week after coming back, what is it about Taipei that has stuck in my memory?

Men’s hairstyles, for sure. Indeed, every time I saw someone with his hair spiked sideways like a fan, I had to wonder: isn’t he driving a scooter, like everybody else? And so, doesn’t he have to wear a helmet? I still don’t understand how they manage.

In most cities, an address is a simple two-dimensional thing: you give the name of the street and the number, like 742 Evergreen Terrace. Sometimes, a street may have a North side and a South side, or a East side and a West side. So you may have to say 129 West 81th Street.

In Taipei, this is just the start. Each major street, besides possibly having a North and a South (or East and West) side, is divided into sections, each section being about one or two miles. My hotel, for example, was off Zhongshan North Road, Section 2. Now, this is just the beginning. Side streets of main roads don’t get a name, but rather a number, as if the street itself had a street address. So my hotel was on Zhongshan North Road, Section 2, Lane 11. Now you can add the number of your building and have your address. Unless, that is, you are in a side street of the side street. Such side-squared streets are called alleys (in the English standard translation). This, for example, is the name of such a street:

I want to stress once more: this is just the name of a street, not a complete address. It’s like the sign near my place that says “18th.”

Both at the museums and at the clubs that we went to, we found lockers instead of a coat check. It works very well, especially in clubs. It is safer, and there is no queue. It is a bit odd that a corner of a club would look like a gym, but you get used to it. I was reminded of my first entrance in a club in Beijing. The coat check had a long line (which was brazenly jumped by a person while I was waiting), at the end of which there was a short but wide woman in a tiny coat check room, completely surrounded by hanging clothes. She was wielding a sort of broomstick with a hook on it, that she used to hang clothes on hooks that were running all over the walls. She said something in Chinese to me when I gave her my jacket. Someone translated for me. “She says to look where she is putting your coat, so you can tell her where it is when you pick it up.” Evidently, the number of my coat check ticket had no relation with the location where she hanged it.

The club that I liked in Taipei, besides the lockers, had good music and a nice vibe, as already reported. The cover charge entitled each of us to two drinks. When I asked for a beer, the barman gave me a warm beer. (It was Heineken, not Guiness.) When he saw my face when I started drinking, he helpfully offered a glass full of ice. I remembered reading about the warm beer on the web, but assuming it was just an urban legend, like the friendly shopclercks. And so I had two warm beers that night, and two more the following night. You can’t let something free go to waste.

The following monday, I was taken to an “all you can drink” night. For a substantial cover charge (about US\$15) one could have any drinks all night, and there was a DJ, a dance floor, and quite a few people for a Monday night. A sign at the entrance informed the patrons that there was an extra charge for spilling drinks on the floor or for throwing up. We did not stay long enough to see if anybody was charged extra that night.

It was only in the last night that we had some dignified drinking. We went to a small, nice place called Bistrot near the Taipower Building stop of the subway, which I highly recommend to any other theoretician who should happen to visit Taipei. They had a very wide selection of beers, including, amazingly, Chimay, which was served in a proper Chimay glass. They also had Hoegaarden, and pretty much anything you can name.

Kekou Kele?

One day, I drank soda with lunch in Taipei.

The other side of the bottle is more familiar.

The chinese label reads 可口可樂: in pinyin that’s ke kou ke le. The ‘ou’ is pronounced ‘o’ (for example, the common name Zhou is pronounced like “Joe”) and a final ‘e’ sounds similar enough to the ‘a’ in “cola,” so the Chinese name sounds sort of “caco cala.” Why isn’t the Chinese name 口可口樂? Apparently, the other name sounds better.

When looking for the Chinese name of a foreign brand, it is common to privilege the “niceness” of the name over the phonetic faithfulness. Google’s Chinese name is 谷歌, which is gu ge in pinyin and it means something like “song of the valley.” Perhaps what they did was to privilege phonetics, instead. (There is, by the way, an online petition to ask Google to change its Chinese name.)

This also came up when, in Beijing, it was decided that I should get a Chinese name. I suggested something that would sound like lǔ kà or lú kà. Apparently, however, either there are no such characters, or they would not sound nice. So far, the best we have come up with is 路卡, which is pronounced lù kǎ and is pretty good phonetically. The two characters mean “road” and “block,” respectively, so together they could mean “road-block,” which is a good name for a professor, except that they are never used together with that meaning. To me, 路课,lù kè, would also sound good: here 课 means “class” (as in “lecture in a course”) and 路 means “road.” But, I am told, you can’t have two 4-th tones in a name. “How are you going to call out a name with two 4-th tones?” Oh well, I hand’t thought of that.

See, this Chinese name business is not easy. I know that there are a few Chinese speakers who read this. Any suggestion that is better than 路卡?

Going to STOC and FOCS

With the exception of STOC in Montreal, where I could not go for a visa problem, I have been to every STOC and every FOCS since STOC’97. The official (and historic) purpose of scientific conferences has something to do with the rapid dissemination of research results. In reality, most papers presented at STOC/FOCS had long been disseminated before the conference takes place. There are many other reasons, however, why I like going to these conferences and why I think they are important.

For one thing, they keep our community together. Over time, the scope of theoretical computer science increases, as we become interested in more and more subjects, like error-correcting codes, quantum computing, game theory, and so on. I think it is very important that we have a single place to go to, where results on all these subjects are talked about, and where people can notice connections between what they do and the new things they hear about. Avi has already discussed very eloquently the need to keep in touch with what other theoreticians are doing, so I will refrain from repeating his points. I just want to say: can we have single sessions in STOC too?

This STOC in Seattle had one of the strongest programs among conferences that I can rememeber. There were perhaps four papers each of which would have easily been considered the best paper at some earlier FOCS/STOC. Indeed, the quality of most papers was outstanding.

Most talks were very good too. James Lee says that the reason he goes to talks is that often the speaker will say one sentence that gives some insight that would have been very hard to extract from the paper. That sentence, he says, is what makes the talk worthwhile. He is quite right, and, indeed, someone who went to several talks and who writes often on the web should collect these sentences and put them online. The 20-minutes format helps. It is very hard to prepare such a short talk, but the time constraint puts some pressure to cut to the chase and just say what the paper is about and what new ideas are there in the proof. Among several other talks that I enjoyed (such as Anup Rao’s and Irit Dinur’s), I liked Guy Kindler’s talk on this very technical result. I can’t say how well he explained the problem, because I was already familiar with it, but I think his explanation was very clear. With a few minnutes to spare, he started to talk about their very technical proof and he gave an explanation for “why” the result is true that was very clear and that I had not gotten from reading the paper and thinking about related questions.

Normally, another reason why I enjoy going to FOCS/STOC is to see my far-away friends that I get to meet only once in a while, and to catch up with what is new in life and in theory. In this conference, however, I went to talks in almost all the sessions, except when jet lag made me oversleep. (Hence I missed the session on zero knowledge and Russell Impagliazzo’s invited talk, which were highly praised by those who attended.) In fact, a few times, there were two talks that I was interested in that were scheduled against each other. Bad parallel sessions, bad, bad, parallel sessions!

By the way, I am aware of a problem here. If there are single sessions then fewer papers can be accepted, and if I thought that almost all papers were so good, how can I support a system that would have led to the rejection of some of them? Well, by now my readers know that coherence is not the strong point of my posts. I don’t know, maybe we should have a four-day conference. Or maybe the good rejected papers would be resubmitted to FOCS in Berkeley. Perhaps, by random fluctuations, the quality of the other submittd papers will not be so high, and things will even out.

Which reminds me: people who attended the business meeting at this STOC and at the previous FOCS might have some doubts, but I hear that, yes, there will really be a FOCS’06 in Berkeley.

Not that there is anything wrong with it

Monday, for lunch, six theoreticians head from the STOC conference hotel towards the fish market. It’s four Israeli, me, and another non-Israeli. We get our halibut sandwiches and we go sit by the waterfront.

Someone walks by. “Hey, you look Israeli,” he says pointing in our general direction, “are you from Israel?” Blank stares from us. “Hey, it’s ok if you are,” he says as he walks away.


On Monday I gave my talk on pseudorandomness and combinatorial constructions, and the whole Taiwanese complexity theory community showed up, all six of them. They are working on my favorite problems, like amplification of hardness, seedless extractors, locally decodable codes, unique games and so on, and we had a good discussion after the talk.

On Tuesday, Chi-Jen took me to see the Palace Museum, that contains Chinese decorative art and calligraphy including extremely old pieces. This is mostly objects that the fleeing Kuomingtan people took with them when they fled from mainland China. Much destruction of art and antiquitities went on during the Cultural Revolution, and so taking these pieces out of the country actually saved them.

Taipei is not a city of architectural wonders, but it has a few beautiful temples. The one I saw is very close to a domestic airport.

I spent the afternoon in Danshui, a pleaant neighborhood by the river.

We got there around 5pm, just when the schoolkids where returning home, and people were coming back from the offices, the night market had just opened, and the place was quite alive. In the middle of all this, someone was practicing calligraphy on the street.

In Danshui, I saw the only funny sign of this trip.

And the thing is, this was for a parking spot in a designated parking area for scooters. The same in Taipei, designated parking areas for scooters have a few spots reserved for the disabled. I have to say, it looks a bit bizarre: a disabled person riding a scooters? Indeed, there are three-wheeled scooters that are driven by people that walk with difficulty. (They are not at all like the small electric ones that are used in America, these ones have regular internal-combustion engines, and they are definitely not meant to be used indoors.)

Finally, this store in Danshui had the most arresting name.

Not the usual place

Sometimes, even in very interesting cities, the club scene offers no surprise. The place closest to my apartment in San Francisco has a dance floor, and two spaces to hang out, each with a bar. On weekends, the dance floor is really crowded, and one can barely move. That is, until you hear

I don’t wanna hear, I don’t wanna know
Please don’t say you’re sorry

and then you cannot even move any more.

In Beijing, the place we went to has also two rooms to sit down, two bars, and a crowded dance floor. And then

I’ve heard it all before
And I can take care of myself

and it gets really crowded.

I was expecting more of the same in Taipei, but I was pleasently surprised. For one thing, the place we went on Friday had only one bar. More significantly, one guy was singing, and a screen was showing some music video. I was afraid we had found Karaoke night, but then the video featured the same guy who was singing. If I got it right he was Fan Ri Chen, a local celebrity. Later the music was a mix of the usual and of Mandarin pop, including Mandarin renderings of famous Western songs. The dance floor was already packed, but then we heard


and everybody came to dance. Sorry played, of course, but nobody payed much attention.

Update 5/24/06 YouTube has the video of Ai De Zhu Da Ge (爱的主打歌), the song that I liked. The video is embarassingly bad. They also have a song that Hoeteck likes.

Mother’s day in Taipei

On Sunday we briefly hanged out in a shopping district.

A Malaysian singer, “Gary,” who is apparently a big Mandarin Pop celebrity was performing on a stage to advertise his latest CD. Seeing at it was Mother’s day, he was periodically joined on stage by his mother.

Hoeteck was there before me, and he told me that earlier they had a skit where the mother brought the singer some soup on stage, and then fed him with a spoon.

Being too late in the day to visit any major museum, we moved to the MOCA (“C” is for “contemporary”) where, of all things, they had an exhibit of Italian fashion design. We then recamped to a cafe in Ximending, a neighborhood that I would call “yuppie.” Locals who are around my age consider it “the place where college students hang out,” although college-age folks belittle it as “the place where high-scholl kids go.” I was not able to check with any high school student whether this kind of looking-down goes any further. In reality, Ximending has pleasent cafes, nice shops, and a mixed crowd.

Eventually, it was time to move to the Huaxi night market, which is famous for the restaurants that sell snake soup, snake meat, and liquors made partly from snake blood. Each such restaurant has a hawker in front advertising their stuff, and some of them handle a live snake. Every now and then, they feed a hamster to the snake, or even kill and cut open the snake in front of onlookers, but we were not lucky enough to see it. In front of each such restaurant there is a sign, in English and Chinese, that says “no pictures.” I was wondering why, and then I noticed another sign that said “none of the snakes served here is a protected species.” I did sneak one picture, anyways. These are preserved snakes, or something:

Hoeteck had been looking for Taiwanese eel noodles ever since tasting them in a Taiwanese restaurant in Boston several years ago. Apparently he never found such good eel noodles anywhere else. We found some good eel noodles in Huaxi, but apparently they were not as good as the Bostonian ones.

Rocks, giants, and more dumplings

On Friday Hoeteck gave his well-received and well-attended talk. Later Chi-Jen took us to have dinner at Din Tai Feng, famous for its dumplings. Their specialties are the steamed dumplings called shao long bao, which they make with soup inside. How do you get soup inside the dumpling? (Think about it for a bit, the answer is at the end.) The kitchen is at the center of the restaurant, and it has glass windows all around. The cooks all wear white shirts and surgical masks, and work around a big table. The image of an operating room is very strong. The dinner was great. Later we went to Taipei 101, the “tallest building in the world.”

On Saturday, Chi-Jen took us to Yehliu, a seaside town famous for its rocks that have been eroded by the sea into amazing shapes.

Some of them look like mushrooms

This is the “sandal”

And this is the “Egyptian head”

But first, we stopped at a restaurant where we picked our favorite fish and crabs from an aquarium and had them cooked to order. The huge fish, which yielded three different dishes (sashimi, soup and grilled) was surprisingly cheap.

A religious festival of some kind was also going on. The parade included men dressed up as giants.

One can see the head of the person driving the giant showing up in the giant’s belly.

There was a market of sort next to the park with the rocks. They were selling snacks such as these. (The ones closer to the camera are wasabi “chips”, quite spicy.)

Here is how these flat things are made flat.

There was a lot more being sold in the market.

So, how about the dumplings? The soup is frozen, and a bit of frozen soup is put in the dumpling when it is made. When the dumpling is steamed, the frozen soup melts.