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.

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.

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.

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.

What phone booths are good for

There is a phone booth at the street corner by the Institut Henri Poincare in Paris. What are phone booths good for nowadays that everyone has a cell phone?

Someone found a use for it: a man lives there. The floor is made of metal, but there is a blanket. We can see the figure of a man in a thick sleeping bag (this is January, and the temperature is often freezing). The space is too small for him to lie down, but he can sort of crouch down, and the glass walls protect him from the wind (and from the rain: in Paris it rains roughly every other day). But there is a one-inch gap between the two doors. I would still be cold, and the sleeping position would give me a stiff neck.

Sometimes I walk by and he is not there: only his covers are there. Is he not afraid that they will be stolen? Perhaps he got chilled and went to sit on a subway vent to warm himself in the hot air coming up through the grates. But mostly he spends his days in the sleeping bag, hibernating.

Beauty, Approximation, and Inapproximability

This past week I attended a workshop on approximation and inapproximability at IHP. Once during a talk I stepped back. Usually when that happens the thought is: "Words, words, words. What is the point of all this? What am I doing here?". But this time the thought was one of awe: "Beautiful! This is beautiful".

The fog of unknowing covers the computational structure of the world. Sometimes a paper is published that sheds light on one problem or one technique, novel but highly specialized. Now the fog is lifting and we are discovering the structure connecting those problems and results. The scenery is coming into focus. It is an exciting time to be in TCS!

Best technological advances for technophobes

Yesterday I discussed technological advances with friends who are technophobes. What new features do we like the most?

- years ago, when I first had a wifi connection at home, it changed my life. I suddenly started carrying my laptop around and using the internet constantly for everything (when is the next bus? what shall I make for dinner? how can I deal with this or that problem of the moment, such as opening a bottle of wine without a corkscrew, helping my niece with Math, and what not). I would not have predicted that the small change from cable to wifi would have such an impact on my life! But now I am finding that there is a downside to that flexibility - when the internet is at my fingertips at all times, suddenly there is much less time for quiet reflection, or research, or reading books, etc. On balance I think that I had a better quality of life before wifi.

- this year I discovered the tablet as a substitute for blackboard (or whiteboard) teaching. Although I use very little of its possibilities, I still love it and am advocating it with my friends. Never before have I been ahead of the curve in using technological innovations! They are surprised and respond to my enthusiastic assessment with interest.

- a couple of friends last year have been praising the iphone. But I have seen it interrupt dinner conversations and absorb a fraction of its owner's attention at a time when it ought to be directed to the people who are physically present. I fear its invasiveness.

- our lectures this week are being videotaped and will be put on the internet. Will this be revolutionary? I saw at Microsoft thath it could be quite useful, but will this really change the way we work? I am not sure.

- one of my friends yesterday praised synchronization of applications. He said it changed his work life. Now that his agenda, email, documents, etc, are automatically synchronized on his iphone, his environment at work, and his environment at home, that his applications are synchronized to one another, and that archiving is done automatically, it saves him a lot of time that used to be spent on such dull tasks. I am tempted but the comfort of his work conditions, as he describes them, but fearful that it might mean another encroachment of technology onto my life.

Pink walls in Math building

Right now I am spending some time at the recently renovated Institut Henri Poincare, a Math institute in Paris. In the main lecture room, the walls are painted a light but definite shade of pink.

Why pink? Could this be some kind of strange initiative to try, in this male-dominated world of Math, to make women feel more welcome?

Apparently some town in Mexico has some women-only taxis that are easily recognizable because they are all pink.

Those taxis also have special makeup mirrors in the backseat.

But I didn't notice any makeup mirrors at IHP.

Looking for a PTAS for Maxcut in less dense graphs

There is a PTAS for Maxcut on dense graphs, i.e. with average degree cn.

Wouldn't it be interesting to have a PTAS for Maxcut on slightly less dense graphs, say graphs with average degree cn^{1/3}?

The dense graph PTAS is based on taking a small random sample S of the vertices, guessing which of those are on which side of the unknown optimal cut, and using the edges between S and the rest to place the other vertices somehow (several algorithms exist for the "somehow").

In less dense graphs, one might hope that many vertices of S, within distance 3 (if you take a random walk of length 3), reach Omega(n) vertices of the graph. So why not take into account S, not just from the perspective of adjacent vertices, but locally, within a limited neighborhood?

2

2 is my least favorite number. It keeps playing tricks on me.

The other day after presenting a simple 2-approximation I tried to show a complicated, improved 3/2 approximation, but a factor of 2 somehow disappeared along the way, and I ended up with a proof that my more complicated algorithm was a 3-approximation! That happens to me all the time, and, strangely, it always seems to be the 2's and the 1/2's that disappear. The 5's and 7' are much more serious and responsible. Once they come, they stay. They don't go away without reason.

2's look naive and honest, but they are immature (have you noticed how they always come up at the first half-baked attempt to examine something?) and one should beware of their taste for pranks.

Proof by silence

What is a proof by silence? The speaker makes a statement. They say: "Proof". They then stop talking, leaving silence hanging for a few moments. When they see several people nodding in the audience, they say: "End of proof", and move on to the rest of the talk or lecture.

Why? When a statement is straightforward for the audience, it may be easier for them to figure out by themselves why the statement holds rather than listen to an explanation.

Example: For an audience of graduate students and researchers, the statement: "Every graph with maximum degree d is can be colored with d+1 colors" is straightforward.

Approximation Algorithms and Structural Complexity

In Approximation Algorithms, we try to go as far as possible towards constructing an approximation. In Complexity Theory, people try to go as far as possible towards proving that a problem is not approximable.

There is a natural meeting point, at the limit of our respective searches -- the instances for which we have the greatest difficulty designing approximations are precisely the instances for which, on the other side of the barrier, people try to prove lower bounds. Ultimately, it is the same combinatorial structure that frustrates our attempted algorithms and that provides the ingredients of their lower bounds.

The researchers, like me, whose domain of specialty is algorithms, work on only one side of the barrier, but the ones whose particular strength, at the core, is in combinatorial structure, can work on both sides.

How to present algorithms: correctness level and runtime level

When presenting an algorithm, it can be non-obvious that the algorithm does output the desired result, and also that it does it in the desired runtime. Sometimes it is convenient to present the algorithm at two levels:
-at the correctness level, put in just enough detail to enable the proof of correctness;
-at the runtime level, add just enough data structure and implementation details to enable the proof of runtime.

For example, at the correctness level Prim's algorithm is very similar to Kruskal's algorithm and can be presented using Tarjan's red-blue coloring approach in his green-blue book. At the runtime level Prim's algorithm is very similar to Dijkstra's algorithm (they both use heaps).

Mixing the two levels is frustrating: when proving correctness, one has to deal with low-level details that unnecessarily clutter one's understanding.

When should deadlines be set?

On December 31, as an editor, I received one late referee's report, and one revision of a submitted paper. Obviously some people are serious about New Year Resolutions! So, it's good to set Jan 1 as a deadline.

As an editor I have given up on setting deadlines for reviewers, asking them instead to set their own deadline themselves, in the hope that they are more likely to respect it then.

As a teacher this year I have let my TAs influence me and set most deadlines for assignments at midnight. Students at Brown reputedly go to bed at 2am on average, and "don't really get all they could from their life at Brown if they go to bed before midnight, since that's when things start happening". (Those "things" do not include lectures as far as I know.)

As a person, I am so glad that I am beyond the student stage and that most of my deadlines are now "soft" - indeed, I am chronically late, always, everywhere, and in everything. How ironical for me to penalize students for not respecting rules (such as turning reports in on time) that I would have the greatest difficulty following myself. Fortunately the TAs, who tend to be serious students with good self-discipline, are usually so convinced that it is right and just to set those rules and to enforce them, that I am swayed by their conviction.