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!
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!
posted by Luca at 7:18 AM
1 Comments:
3/31/2006 04:29:00 PM
Could we know whether their results on lower bounds for local search problems published yet (or available anywhere on web)?
Post a Comment
<< Home