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.