Summary
Today we show how to construct an inefficient (but efficiently verifiable) signature scheme starting from a one-time signature scheme.
Next time we shall see how to make it efficient using a pseudorandom function.
Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.
This Onion article was published in January, 2001. (via Penmachine)
It is time to get a new laptop, and I would like it to be as light as possible subject to having a full-size keyboard and a not-too-small (at least 12”) display. So it is down to the MacBook Air versus the Lenovo X300.
I have been planning to move to OS X, and I appreciate superior design, so the MacBook is the default choice, but I also like to be able to connect a computer to other devices, which leads to the problem described in the video.
There is still time to donate to the No on 8 campaign, and prevent a constitutional amendment that would eliminate same-sex marriage in California. As of the beginning of October, the Yes on 8 campaign had raised about $25 million, of which about 10 millions came from the Mormon church, and another 7 from Mormon families; the No on 8 had raised about $15 million. (The figures have changed substantially in the past two weeks, but I haven’t found a precise reference.) So if you don’t want the Church of Latter Days Saints to dictate what should and what should not be in the California constitution, and you are an American citizen or permanent resident, here is your chance.
Moving on to a happier subject, I’d like to describe what it’s like to eat in a restaurant in Beijing. To make a long story short, it’s fantastic, but here is the long story.
In any nice resturant, each chair has a pillowcase-like thing; one wraps one’s jacket on the back of the chair, as usual, and then one puts the pillowcase thing over the jacket and the chair’s back. This way there is no risk of food spilling on the jacket, and the whole setup is quite aesthetically pleasing.
As we do this, a waiter or waitress, usually the latter, brings one menu to the table, and waits for us to order.
One menu is brought regardless of the size of the party, and when I say menu I don’t mean a half-page minimalist listing of three or four choices per course one may find in the US, the fewer choices the more upscale is the restaurant (culminating in the choiceless prix-fixe menu of downstairs Chez Panisse). I mean a whole booklet, featuring ambiguous pictures and captions. (“Is this fish?” “I don’t know, it’s called ‘delicious three-cooked stew’ on the menu, and to me it looks more like mushrooms.” “But isn’t that the character for ‘pork’?” and so on.)
The waitress will hand over the one menu, and stand there, awaiting for an immediate order. A party of six westerners, say, is going to order ten courses, and each course is going to be discussed (and guessed about) by all six, for a total of at least 60 steps. In one episode, a party of eight took 25 minutes to complete the order (the waitress never budged from the side of the table).
After a short while, the dishes start coming. Except the rice, however. For reasons that no westerner understands, rice is almost never brought to the table when ordered; one needs to ask for it again, sometime three times, and it finally arrives in tiny cups which I finish halfway through the meal.
It could, of course, be worse. At the Little Sheep hotpot restaurant, known for its cumin-flavored soup base, we ordered rice and I noticed the waitress wrote nothing. Then we asked again and the waitress nodded. Then we asked a third time, and finally she said
没有米饭
“we are out of rice.” Out of rice? In a Chinese restaurant? In CHINA? Do you ever go to an Italian restaurant only to be told, sorry, we are out of pasta?
This brings me to another surprising discovery: except on some University Campuses, there are no laundromats in Beijing and there are no laundry stores which will wash and fold clothes by weight. (This has been a bigger surprise than when I moved to San Francisco and I was told that fortune cookies were invented there.) There are, however, dry-cleaning operations, but they are quite expensive by local standards. Recommendation to visitors planning an extended stay in China: bring (or buy) plenty of clothes.
Returning to dining, one has to plead for rice, but it is even harder to get napkins. Very upscale restaurants have cloth napkins which the waitresses pin under your plate so that they hang over the side of the table and your leg. Wiping your face with them feels uncomfortably close to doing so with the tablecloth and appears to not be done. Less fancy places may give a wet cloth to wipe your hands and, upon request, give postage-stamp-size paper napkins. I have taken to always bring a pack of kleenex when I go for dinner. (It should be noted that the combination of no laundry, no napkins, and eating splashy things with chopsticks can be stressful.)
People like to eat early in Beijing, with most restaurants officially closing at 10pm, but often having no customers but us by 9pm or so. At this point, subtle hints are offered that we are overstaying our welcome. Lights are dimmed in other sections of the restaurant, we are told that the kitchen is closing and if we want anything else, we are asked to pay, the kitchen staff comes out to eat, they start washing the floors. In at least one case, the waiters and kitchen staff finished eating and left, leaving behind a couple of waiters to look after us, and we kept eating in the darkened place. Only once, however, (and not in the above episode) were we ever explicitly asked to leave.
The Chinese State Administration of Foreign Experts Affairs has a FAQ page that is worth a read. Check out Why do the Chinese people always stare at foreigners?.
I am spending a month in Beijing. This week the China Theory Week is under way, the second in a series of annual events bringing graduate students from all over to Beijing for a week of talking about theory.
In October, there will be the China Symposium on Theoretical Computer Science, which is like the Theory Week but with older people.
Yesterday I spoke about my work on spectral methods for Max Cut, on which there have been a couple of advances since I posted about it here: (i) Moses Charikar has improved my analysis of the recursive algorithm, and (ii) I am now able to handle (in a complicated way and with very poor bounds) the “Max Cut Gain” problem.
I will write about it here, but first I will have to find out how to do it. WordPress is blocked, I have not been following all the explanations about “tunneling” and “proxy servers,” and so far the only way I have found to post here (open a remote desktop on a Berkeley computer) is excruciatingly slow and not conducive to write math (which needs previews etc.). Meanwhile a revised paper is available online.
