Monday, February 14, 2011

What happens when I have an idea for a proof

"Then, as he rode along, he composed a sonnet, fitting to his case, the strength and rhythm of which seemed to him, as he sat on his horseback, to be almost perfect. Unfortunately, when he was back at Clavering, and sat in his room with the pen in his hand, the turn of the words escaped him."

Trollope's words would just as well describe what happens to me after I have had an idea in a setting where there is no pen handy.

Glimpse of another life

"And he said to me: "Don't give me soup! I just got out of jail!""
(Overheard on the bus this morning)

Friday, February 11, 2011

Best memories of being on a program committee

The first program committee on which I served was SODA in the last 1990s. It was eye-opening for me. Never before had I heard frank discussions about what made some research questions "good" and others not so good. Never before had I heard in-depth discussions on what made a result worthwhile. It was a great education.

Previously, it was always a mystery to me how one would pick a problem to work on, and my choices were impulsive and not reasoned out. My criteria used to be: "Is it fun? Do I feel like working on it? And [after working on it a while:] Am I getting anywhere?" Afterwards, I could assess possible research directions in a much more systematic way.

In addition I also learned that many of those questions are discussed by mulling over the introduction of the submissions, and that helped me organize my writing and figure out what to put in the introductions of my subsequent papers.

For people who went to graduate school at a place where there is a tradition of forming PhD students in those matters, being on a program committee might not be such a big deal, but for me, it was a great experience that affected my research methodology.

Friday, February 4, 2011

Soft-spoken?

I have learned indirectly that some students find that I am soft-spoken in class, so they have trouble hearing me.

A long time ago, I was a really loud teacher. Then I took a few voice lessons, became protective of my vocal chords, and dropped a good number of decibels. Not enough voice practice to learn to project my voice far while keeping it nice and relaxed, unfortunately.

I also like to believe that a relaxed voice sets the tone for a more relaxed classroom atmosphere, where people are less nervous about asking questions. Whether that's true or not, I have no idea. (Has it been studied, even?)

So, what to do about this?

I suppose that a microphone could be the answer, although I am not sure what effect it has on class dynamics. It might become more like a show and less like a group endeavour.

Thursday, February 3, 2011

Combinatorial enumeration in society

In casual conversation, it is normal to automatically pick up small clues to figure out people's relationship to one another. A glance of mutual understanding, a disparaging remark often suffice to identify couples. How much information is needed to figure out who is paired with whom?

In a group of six people, three men and three women, it usually doesn't take long to figure it out. Indeed, there are only 3.2.1=6 possibilities. But recently, conversing with a group of gay men, I was surprised to find that I couldn't do inferences as usual. Why not? It's simply a matter of combinatorial enumeration: with six men there are 5.3.1=15 possibilities instead of 6.

In general, assuming perfect matchings, with k men and k women there are k(k-1)(k-2)... 1 possibilities. With 2k gay men, there are (2k-1)(2k-3)...3.1 possibilities.

Wednesday, February 2, 2011

How program committees shape the field

Today I got a STOC submission rejected. It's a technical result on which I (along with my coauthors) spent many months to build a fragile construction of techniques that had to be tweaked to fit together in just the right way. I had been working on it off and on since 2007, if not earlier. From a purely technical viewpoint, it may be my most intricate paper ever. So, what to make of this rejection?

Maybe they didn't like the paper because of all of its technicalities. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.

Maybe they couldn't follow the arguments. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.

Maybe they didn't appreciate the difficulties and thought it was poorly written. In which case, in order to get papers accepted in the future, I should stick to less complicated projects.

Maybe they didn't care for the result. In which case perhaps my time was not well invested - huge amounts of time spent solving a problem that people apparently don't care about. In which case, in order to get papers accepted in the future, I should stick to projects with a more immediate appeal.

Maybe the paper really was poorly written. Yet we spent months just on the writing, which was almost beyond us. Am I up to spending another couple of months on this proof to try and see if it can be streamlined? I don't think so. In which case, in order to get papers accepted in the future, I should stick to less complicated projects, where I master the big picture.

Maybe they were not impressed. I only imagine it's difficult because my brain doesn't work as fast as it used to when I was a student, but, actually, that result is not that hard. Hmm... I don't like that idea. I will need more evidence before I'm ready to entertain that possibility!

I had been planning to devote a good part of my time working on follow-up projects, digging deeper in even more technical developments. Maybe I should reconsider.

Or maybe I don't care. After all, what's tenure good for, if not to pursue our research interests even when the wind of fashion (or the majority's taste) blows in a different direction?

But maybe - gasp - a reviewer found a mistake in the proof! Since that proof is a bit too big to fit in the cache in my brain, I was only able to check it one part at a time, so an error is a real possibility. That's a worrisome thought... what if the result of our efforts fell apart?

Then, there is also the problem of advising students: maybe this rejection suggests that this research direction is not a good one to steer them towards, because it's high-effort, low-reward, and would not be good for their future job applications. That's another concern.

And that is how program committees shape the field.

Monday, January 31, 2011

Some old advice from Andy Yao

When I was a graduate student, I had the good luck to do some research with Andy Yao. Here is, as best as I can remember, one piece of advice that he once gave me and that I have repeated to students a number of times since then:

When you get a paper accepted to a good conference, the main effect is that it buys you some time: some number of weeks or months during which the pressure to publish is off and you can focus on exciting but very hard open problems. Thus, your work should be organized to achieve a balance between projects that will probably improve your vita, and projects that will most likely not get you anywhere in the short term, but that are important in the long term.

Saturday, January 29, 2011

Grading system

In French high schools, grading is in the range [0,20], and typically follows a Gaussian distribution centered at 10 or 11 and with standard deviation about 2.
The correspondence with US letter grades is roughly as follows in my opinion:
A+ 16 and above
A- 14 and above
B 12 and above
C 10 and above
Fail below 8 (makeup exam between 8 and 10).

In US high schools, it seems that grading is roughly as follows:
A 93 and above
B 85 and above
C 78 and above
Fail below 70 (D between 70 and 77, whatever D means)
Weird because most of the information is in the neighborhood of 100.
It makes more sense to think of the complementary measure, i.e. the distance to 100:
A 7 and below
B 15 and below
C 22 and below
Fail above 30 (D between 23 and 30).

This mean that in France, exams are design so that the typical student will be able to answer slightly more than half of the questions, while in the US exams are designed so that the typical student will be able to answer most of the questions.
No wonder my students at Brown say that my exams are particularly challenging!

From an information-theoretic point of view, the French system yields the most information.

Friday, January 28, 2011

Snow

There's nothing quite like finding your driveway snowed in when returning from a transatlantic trip.
After a little bit of shoveling to clear the wall of packed snow built by street plows, I drove over the snow with a running start, only shoveling when the car got stuck. After three or four tries I got in. Similarly one might write a paper by just going through the proof quickly, fixing bugs as they come up, and hoping to get through in the end.

I remember shoveling snow with a friend who insisted on removing every little bit, for fear that it might turn into ice later. That same friend is a perfectionist when writing papers.

Wednesday, January 26, 2011

The never-ending travel

On my trip from the US to France last month, I was forced to spend Christmas night at an airport hotel.

On the return trip from France back to the US, I am now forced to spend another night at an airport hotel.

Ah, travel. There is a Pat Conroy quote that starts with:
“Once you have traveled, the voyage never ends".
That's how this is starting to feel.