How to enjoy writing?

Some time ago I received an email asking if I had any opinion on how to enjoy writing papers. That's a tough question. We usually fumble trying to come up with a good problem, struggle while having some fun formulating a good conjecture, delight in trying to solve it, and finally have a painful time writing the resulting paper. How can we make the writing stage less painful?

One thing I learned recently about this, is that it is not a good idea to try to fit writing into the cracks of free time, and not to delay until the environment is not favorable to problem-solving. I had one visitor come for a month -- four weeks: we spent three weeks plus a little bit working on formulating and solving a problem, then he declared, to my surprise, that he would spend the last three or four days of his stay writing up what we had done. It was the right thing to do, of course. For busy people, it's a really smart idea to plan significant time for writing hand in hand with problem-solving!

Another thing I learned is that giving talks helps while writing. It helps clarify one's thoughts and maintain one's interest.

Ideally, I suppose that with self-discipline one would maintain writings of one's work during the process of doing the research, but it's real work to incorporate a day's discussions in a file in an intelligent way, synthesizing it with previous notes and remarks so that the file does not grow out of bounds in a chaotic manner. Still, my impression is that writing is more fun if it happens at the same time as problem-solving, in spite of knowing that everything will probably need to be rewritten at some later time.

Are there good tips from the world of programming? Not tips to write well-organized, coherent, clear papers, but tips to write in a way that keeps that activity enjoyable (or at least, enjoyable to some degree) at every stage.

Memorial day weekend

This is Memorial day weekend, during which Americans celebrate their veterans and remember their war dead. The liberation of France is the first reason why I have so much admiration for Americans (and the British and the Allies, of course). Here is an excerpt of a journal entry written by my grandfather (my father's father), describing the joy of the population at the liberation of Versailles. A book gathering his writings about being a professor at the Sorbonne during the Occupation has been submitted for publication.

Vendredi 25.
Au réveil, soleil radieux et silence complet sur Versailles. A peine quelques bruits de canon très lointain. Une fumée s’élève dans le Nord. Qui est vainqueur ?
A 9h, nous sortons mon fils et moi. [...] Un avion de reconnaissance canadien est tombé avenue de Paris devant le lycée de jeunes filles [dès l’après-midi, son fuselage est couvert de fleurs et de rubans.]. [...] Sur l’avenue de Paris, la foule se presse, plus dense qu’on ne l’a jamais vue aux plus grands jours de fête (aujourd’hui 25 août, fête de Saint Louis, patron de Versailles).
10h50. Débouchant de l’avenue Thiers (à présent ‘Avenue du Général de Gaulle), venant de Rambouillet où ils ont été alertés hier matin, les motorisés de la division Leclerc (spahis marocains, fusiliers marins, éléments du 3e régiment de marche du Tchad) apparaissent. Les acclamations redoublent, si fortes qu’elles couvrent la voix des haut-parleurs. La ruée de la foule est telle que les chars doivent s’arrêter. Les jeunes gens, les jeunes filles, les enfants acclament les chars, couvrent de fleurs et de baisers les hommes, les uns presque enfants à figure rose, les autres (sans doute les anciens du Tchad et de Libye) tannés par le soleil. Les soldats, étourdis par les acclamations, se bouchent les oreilles, jettent à la foule cigarettes, tablettes de chocolat, boites de lait condensé. Le colonel commandant la colonne [note: Lieutenant-Colonel Rémi, des spahis marocains.] paraît à la fenêtre de la salle des fêtes de l’hôtel de ville et prononce une allocution si hachée d’acclamations qu’on n’en entend que quelques mots. Un disque diffuse la Marseillaise ; mais les gorges, enrouées d’acclamations ou d’émotion peuvent à peine l’accompagner. Mon fils applaudit frénétiquement, agite son éventail tricolore, hurle : « Bravo ! ». Les enfants sont les plus enragés ; depuis quinze jours ils sont accrochés à la TSF ou préparent les drapeaux, drapeaux fanés ressortis des greniers ou des caves, ou bien morceaux de linge blanc passés hâtivement à la peinture ou au crayolor. [...]
A 21hs 30, nous nous rendons devant la mairie où stationne une foule un peu moins dense que le matin, mais tout aussi enthousiaste. On a retrouvé de la voix pour chanter la Marseillaise . Des haut-parleurs diffusent marches et chansons militaires. Les pompiers ont mis en marche leur groupe électrogène de secours et illuminent la façade de la mairie écornée par l’attaque allemande du 24. Tous les éléments jeunes (soldats de Leclerc dont les voitures stationnent aux environs, pompiers, jeunes gens de la D P, secouristes de la Croix Rouge) se prennent par la main et partent en une immense farandole (note: Le lendemain les pompiers de service prétendront avoir retrouvé 35 talons de souliers dans la cour de la mairie). A 22hs 15, une nouvelle Marseillaise ; puis l’on se retire pendant que les F F I s’organisent en postes de garde.

Friday, August 25. In the morning, the sun is bright and there is complete silence over Versailles. We barely hear the very distant sound of a canon, and see smoke on the North side. Who is the winner? At 9am, my son and I leave the house. A Canadian scouting airplane has fallen on the street "avenue de Paris" in front of the girls' high school. (In the afternoon, it will be covered by flowers and ribbons.) On the street, a great crowd is pressing, denser than I have ever seen it (today August 25 is the feast of Saint Louis, the patron saint of Versailles.) At 10:50am, arriving from "avenue Thiers", coming from Rambouillet, the first tanks from the Leclerc division appear: Moroccan spahis, marine shooters, members of the 3rd infantery regiment of Chad. The cheers from the crowd redouble, so loud that they drown the voice on the loud speakers. The crowd is rushing forth with such eagerness that the tanks must stop. Young men, young women, children cheer at the tanks, cover with flowers and kisses the soldiers, some still almost children with pink faces, others (probably Chad or Lybia veterans) deeply sun-tan. The soldiers, overwhelmed by the acclamations, cover their ears. They throw to the crowd cigarettes, chocolate bars, boxes of condensed milk. The colonel leading the troops (note: Lieutenant-Colonel Rémi from the Moroccan spahis) appears at the window of the city hall and gives a speech accompanied by such cheers that we only hear a few words. A record is playing the "Marseillaise", but the people, their throats hoarse from cheering and emotion, can barely sing along. My son claps frenetically, waving a French flag, screaming: "Bravo!". The children are the most excited. For the past two weeks they have been listening ceaselessly to the radio and preparing French flags, old flags taken out of dusty attics or basements, or pieces of white cloth hastily covered with paint or felt pen. [...] At 9:30pm, we go to the city hall where the crowd is slightly less dense than in the morning, but just as enthusiastic. We have found our voice again to sing the Marseillaise. Loud-speakers sound off marches and military music. The firemen use their backup electricity equipment to illuminate the building, slightly damaged by the German attack of the 24th. All the young people (soldiers from the Leclerc division, whose cars are parked nearby, firemen, young men from the civil protection, Red Cross workers) hold hands and form a gigantic farandole (note: on the next day, the firemen claim to find 35 shoe heels in the city hall courtyard). At 10:15pm, another Marseillaise: then we go home while the Resistance sets up the night watch.

How to test blog moderation?

I discovered two days ago how to change the settings of this blog to allow anonymous comments, which I did. The next day, an anonymous comment appeared (about the move to living in virtual reality): "you still have to go number 2 physically though ... " Thus I am immediately faced with a deep, fascinating question: to delete or not to delete, that is the question.

I occasionally participate in blogs, and my comments often get deleted. For example, once I tried to put a comment on Archbishop Dolan's blog, correcting some information (about the sexual abuse scandal, if memory serves) by giving a few facts, with links to supporting documents. But my comment never appeared. I was surprised because it expressed no opinion and only stated facts. How can one object to that? That blog sometimes contains criticisms in the comments, so I had not thought that comment moderation was unfair. I spent a few days observing the blog regularly after that, and now have a conjecture: the moderator lets through a balance of positive and begative comments, but biases them so that the negative comments are emotional rants rather than rational arguments. It gives the illusion of being open-minded while subtly veering readers in a certain direction. If my theory is true, that's a pretty sneaky manipulation!

Another time, on a similar site, I tried to post a comment. I knew the moderator was ruthless in deleting whatever he didn't like, so I tried to game the system by posting a quote from his own writing, carefully chosen so that in the context of his post it would be a subtle rebuttal of his rant. I figured that he surely would feel guilty about deleting that post, and was hoping to pass his filter successfully because of that. I naively thought I was being clever. What happened next was impressive: my comment got marked as "waiting to be moderated" before appearing... but half a day later. So, yes, it did appear. But by that time, many readers had moved on to some other topic. Additionally, it appeared at the place in the list of comments where I had originally posted it, so it was buried deep underneath all the comments that appeared in the intervening twelve hours, and so I expect that no one read it. Clever! He outwitted me.

So, the main purpose of moderation is propaganda: then moderation is most effective if it does not consist in stupidly deleting everything that does not fit the moderator's agenda, but in letting some carefully filtered, well-chosen criticism go through.

I have lost a lot of my excitement about blogs as measuring the pulse of public opinion, when I realized that comments do not express the vox populi but the moderator's portrayal of the vox populi. It's a sham.

One burning question: how to test such theories? I would love to see some formal study of blog moderation, preferably extended to information control in general. How can the user figure out whether a blog is biased, and how badly? In both of the above examples, I realized it by mere chance, and I did not repeat the experiment. What about blogs that claim to follow certain rules for moderation: how can we verify that they follow the stated rules, when we do not get to see the deleted comments?

Foo and toto

I have always taught my students that "toto" was the French equivalent of "foo" for naming a file or a variable when you don't want to be bothered coming up with a name. Although true in practice, in reality the two words have very different origins.

"foo" is supposedly a misspelling of "f.u.", an acronym for "fucked up" as comes up in the military slang term "s.n.a.f.u." or "f.u.b.a.r.", "situation normal, all fucked up" and "fucked up beyond all repair".

"toto" has a less controversial etymology. It comes from the name of a young boy, the main character in a 19th century play. Nowadays Toto usually appears in childish jokes. It is roughly analogous to "Johnny". When I was 6 or 7 years old my friends and I at school exchanged many jokes about Toto, usually involving pee and poop.

On the other hand, another possible origin of "foo", also from WW2, is that apparently, wherever British troops went, the graffito “FOO was here” frequently showed up. I tend to believe that simply because in that case "foo" and "toto" would have more similar origins.

What is used in other languages? The automatic translation tools don't work for foo!

Cars, buses, and generosity

I had a crazy afternoon mismanaging the sharing of my car with various people. At one point, the car was parked in Providence, I was planning to take the bus to go and get it, then realized that I had left my wallet inside it. I quickly gathered a few coins lying around to pay for the bus fare. As I accidentally took an old 1 French Franc coin instead of US money, I ended up being one quarter short, but the driver was kind enough to let me on the bus anyway.

Then my son called, his friends and he urgently needed their school bags, in the trunk of said car. I told my son to take the bus with me to go and pick it up, but he was just a smidge too late for the bus, and his friend's mom ended up chasing it to the next stop, where I pulled the chord for the bus to stop, and asked the driver to wait while my son got out of the friend's mom's car and ran to the bus door. But then, he had no money! I told the driver: "He doesn't have any money!". The driver stayed silent, not saying that he could get in, but not closing the door either. My son stood silently just outside the open door, not daring to go in without the means to pay his fare. I stared at him helplessly, not knowing what to do. Then a passenger broke the spell and told the driver: "Let him in. I'll pay," got a bill out and paid the fare while my son got on. I could hardly believe it!

Without his help, maybe the bus driver would have closed the door and left. Maybe my son's friend's mother would have had left already, assuming he was taking the bus. Then he would have been stranded alone by the side of the highway and with no money. How quickly the incident could have gone from embarrassing to worrisome! Sometimes we just need a little bit of help. Bus riders understand that. Many of them know what it's like to have been hit but a sequence of unlucky events. They understand solidarity with stranded strangers.

Fukushima information, if anyone cares

Two months ago I was struck by the Fukushima disaster and posted a couple of comments about it. Here is updated information in case anyone is interested in what is happening at Fukushima. I am not sure anyone cares anymore: I don't see much about it in the news! Too boring?

Here's a website with all sorts of raw data: here (there is a menu to pick the language, and English is an option). No data for reactor 4, I guess because TEPCO has not yet been able to send people or robots in to restart measurements.

A quick look on reactors 1,2 and 3 indicates, not that the situation is particularly improving, but that many indicators are stationary. There are still ongoing radioactive leaks. Reactor 1 has something going on: at the end of last week the level of radioactivity inside the drywell suddenly increased by a factor of 5, and has been at that higher level since then; but there is a note on the graph saying "instrument failure", so nothing to worry about...

In general, according to this (H/T to Olivier Devillers for telling me about Sylvestre Huet's blog), the situation is "stabilized" in the sense that the injection of water at the rate of a few cubic yards per hour is sufficient to prevent the core temperature from increasing again.

UPDATE 6/2/2011: blog by a Japanese about Fukushima; recommended news web site about Fukushima.

From rural life to city life to virtual life

In the aftermath of the industrial revolution, most of the population shifted from rural life to city life. No more immediate contact with nature all day long, less and less physical work, and more time indoors in an artificial environment with books and machines.

Now the computer revolution is unfolding, and most of the upcoming generation is shifting from city life to virtual life. Time is spent in virtual social networks rather than with neighborhood kids, playing online video games instead of chess and monopoly, reading blogs instead of newspapers, replacing face-to-face sex with online sex, surfing the web instead of chatting with office mates over breaks, texting in church instead of listening to the homily, finding one's way with a GPS instead of by watching the world outside. The virtual world is a great egalitarian. There is neither Jew nor Gentile, neither slave nor free, nor is there male and female. Even in a wheel chair, you can live your virtual life just as well as anyone else. You are free to create your own persona, unlimited by physical constraints.

How can we do better still, and move to a more fully virtual life?

Our bodies are increasingly unnecessary. But we still need to eliminate the remaining burdens of physical reality. When we go to school, eat, sleep, we are not focused on the online world. Here are a few suggestions:
- game developpers should invest heavily in educational games for the classroom setting, so that children are also in the virtual world during school time. This needs to be much more widespread than now so that children learn from an early age that, whenever they are awake, they need to be engaged with a computer screen.
- food is a big time sink. Why do people not buy more ready meals, but still waste time shopping, cooking, eating, and cleaning up? Food processing companies need to greatly improve their products so that people finally give in. At the same time, farms need to grow less tasty food to diminish the contrast in taste between home cooking and fully processed meals. Progress is being made, but the freedom from food is still a long way off.
- sleep is also a huge time sink, although people now sleep about an hour less per night than thirty years ago. Pharmaceutical companies need to continue investing money on drugs that fight drowsiness.
- the keyboard, mouse and pen are discriminatory against those people who are handicapped, not just in the legs, but also in the arms. In addition using hands and fingers to type and click needlessly uses up muscles and physical energy. So, language recognition needs to be greatly perfected so that we can communicate merely by talking, without otherwise moving. In the longer term, research needs to continue actively on automatic interpretation of signals from the brain, so that eventually we can communicate directly with the computer.
- research on robotics needs to accelerate so that robots take over doing all the tasks of daily life that entail any physical effort.

At that point, we will have succeeded in making the physical world irrelevant, and we will be able to spend our time in a world of our own making, the perfect virtual world, where anything is possible if that is our wish. Oh, what a wonderful vision!

Editor at the Ministry of Truth

One danger of articles consulted online rather than printed or downloaded: online articles can change their stories over time, and those updates can help the present control the past, or at least, control the report of the past. That can be used to correct errors, but also to surrepticiously modify undesirable information.

I corrected an example in my post about Markov's inequality, after a comment pointed out that it was wrong in one interpretation. Added a comment, but whoever reads the post but not the comments will never know. (I could also have deleted the comments to erase the past completely!) No big deal for scientific text, but more dicey for journalists writing about political events in online newspapers.

One partial solution: show your work by displaying text that has been modified. I just did that for the blog post on Israel and France sister countries, using strikeout text. I am rather pleased with the result: the factual error is corrected, but the previous version is still visible. I think that it is better than deletion and disappearance.

Should journalists do that when they modify an article after it's been published online?

How about moderators of popular blogs, should they do that? Rather than delete comments that they don't like, leave them in but strike them out? That would make their bias or objectivity evident, and thus make them accountable to the readers.

How could I live without the internet?

Everyone in my family, including myself, is addicted to the internet. We now have one laptop per person, so that we can spend "together" time, each with his or her own screen. Everywhere I hear reports or remarks about overwhelming screen time.

Imagine I tried to make my home internet-free. Could we survive without the internet evenings and weekends?

It's hard to imagine. Dinner recipes? I would need to get my cookbooks out. Music, movies? I would need to plan in advance what I want to hear or watch. Transportation? I would need to keep my bus schedule accessible. What about arranging for travels, train, flying, hotel reservation etc.? That would have to be done at work, it seems. Friends? Without facebook, some of us would be out of the loop, or we'd have to make plans in advance. Plumber, electrician, garagist? We would need to resurrect the old fashioned yellow pages. Running errands? A combination of yellow pages and phone. Paying bills? Either do it at work, or resurrect the old fashioned checks, envelopes and stamps. Trying to revert to an internet-free environment would require quite a lot of organization!

What would be the upside? Perhaps our books would stop gathering dust on the bookshelves. Perhaps we'd spend more time in conversation, or exercising, or gardening, or in general doing all the things in which one interacts with the physical world. Not that the internet exactly prevents us from doing all those things, but in reality it's a sink that is revolutionizing the way in which we spend our time.

An interactive lesson plan on Markov's inequality

Teacher: Consider the following situation. Driving to work takes you about 20 minutes on average. Is it possible that, with probability 90%, the commute takes you more than 4 hours?
Students: no

Note: Repeat the question twice, once with "90%" and the other with "9/10th" so that each student hears the wording with which he or she is most comfortable. Possibly add specifics about rush hour, downtown, etc, if you need a story to get students going.

The students offer various reasons, but the teacher does not elaborate on them (to save time).

Teacher: Consider another example. You are investing $1000 in some stocks. Your expected return after one year is 5%. Is it possible that, with probability 90%, after one year you will be a millionaire?
Students: no.

Again the teacher does not elaborate (to save time).

Teacher: Now, the question that is the real topic of this lecture. Consider a random non-negative variable X, and way that it's 5 on average. Is it possible that, with probability 90%, X is larger than one million?
Students: no.

Notes:
- take numbers that are so large that the answer is intuitively obvious. It is that intuitive understanding that will provide students with the wedge to understand the meaning of Markov's inequality.
- stress the question that "is the real topic", so that students who are bored because it's too easy for them so far pay attention. Write it on the board just in case.
- why not start directly with the general question? Con of starting directly: at this stage of the course, most students are not yet comfortable with the abstract notion of "random variable", and the examples serve to ground it in reality, reinforcing the teaching of some previous lecture. Con of starting with an example: students might get distracted by the specifics of the example and find reasons that are irrelevant (bus schedule, say), wasting lecture time. Pro of starting directly: I give them only the relevant information, so they're not going to start talking about the distribution r other externals. The best of both world: by starting with, not one, but two examples, stir students away from irrelevance. They should be as similar as possible regarding the numbers used, but as different as possible regarding the context and distribution. They start seeing what properties the two examples have in common, and that directs their thoughts in the right direction. At the same time, that has the side advantage of teaching them a little bit about problem-solving.

Teacher: Why not?

Note: here, do not intervene and let a free discussion between students shape the answer. First, because this does not require particular skills. If they parsed the question, then the "no" answer should be obvious, and you should quickly hear an answer of the form "Because if X was one million almost all the time, then it would have to be more than 5 on average". "Why?" You ask. Eventually someone says something like: "If X is one million 90% of the time, then on average it's at least 900000".

Teacher: Let's formalize that. If X is one million 9/10th of the time, then what can we say about its mean, call it m?
Students: m is at least (9/10)*1000000

Note: when stating the question, make sure to say "9/10th" rather than "90%", to provide a subconscious hint.
Note: repeat the question several times, switching the terms "mean", "average", and "expectation", to reinforce the recent acquisition of that vocabulary by the students, and so that each hears the term which he or she is most comfortable with.

Teacher: What if X is, not exactly one million, but at least one million?
Students: [after thinking about it for a moment] It doesn't make a difference.

Teacher: Let me give you a counterexample. Say that X is, with probability 90%, one million, and will probability 10%, minus one million. [Write those numbers.] Then [write the one-line calculation] X is 800000 on average, so it's not true that, as you claimed, m is at least 900000.
Students: [after thinking about it for a moment] But X has to be non-negative.

Note: place this question right before the proof, as a reminder of that assumption, so that when they have to use it in the proof, it's fresh in their minds.

Teacher: Now, let's extend the problem. If X is one million (or more than one million) with probability p, then what can we say about m?
Students: m is at least 1000000p.

Teacher: Let's extend it further. If X is at least some threshold value v with probability p, then what can we say about m?
Students: m is at least vp.

Note: introduce variable names one at a time. Most people have trouble with abstraction for new concepts, and that makes it easier for them to not get lost by a sudden jump from concrete numbers to abstract algebraic equations. It helps preserve the link between reality and abstraction.

Teacher: Can you prove it? [Then, if no suggestion comes forth:] Remember the definition of expectation. Let's say, to simplify, that X is an integer random variable, so it only takes on integer values.
Students: E(X) is the sum over i of i times the probability that X equals i.

Teacher: actually, in the case it's more convenient to use another characterization of expectation of integer random variables that we have seen before.
Students (remembering): E(X) is the sum over i of the probability that X is greater than or equal to i.
(after some period of fumbling) Aha! So, we can just look at the terms for i=1,2,...,1000000 (v). Each term is at least p, because, if X is at least one million, then X is at least i. So we get p+p+...p, v times, so it's pv.

Teacher: Great. Where did you use the fact that X was non-negative?
Students: (after a blank moment) oh, right; it's necessary for our characterization of expectation.

Note: serves as a quick reminder to reinforce the assumptions behind that equality.

Teacher: You have proved: m>= vp. That's essentially Markov's inequality, but it's usually used, as in the examples above, to prove for variables where m is known, p is unknown, and we use this to prove bounds on p. Can you restate it in that form?
Students: [hesitate, then someone says:] p <= m/v.

End of interactive part, the teacher takes over and writes the final statement of Markov's inequality and its proof, writing it all on the board while the students take notes.

Extra time: Apply the final statement to the examples from the beginning of class. Give the proof for continuous random variables as well (using integrals), pointing out similarities.

Note: Be ready for a different proof. For example a student might say: "The minimum m could be, given our assumptions, would be if X was 1000000 exactly 90% of the time and was 0 the other 10% of the time, and in that case m would be exactly equal to 900000", and then the proof developped in lecture should be built on that insight.

Note: This takes a lot longer than just giving the statement and proof. But it makes the lecture much more interesting for the teacher because we never know what's going to happen, and for the students because they are developing their own insights --- they can have their "Aha" moments. It's also a great way to gauge their level of understanding (or at least, the level of understanding of those who participate.) Hopefully it will help them better remember Markov's inequality. Recapping in the end by writing the statement and proof in full is boring for those students who were most active in the discussion, but necessary for those who are struggling to follow. It can be done quickly, but it has to be done.

"See no evil, hear no evil, speak no evil"

A couple of months ago I was discussing the future presidential election in France with a friend. For the past two days I've been thinking back about that conversation.

- "There does not seem to be a natural candidate for the Socialist party", I said.
- "Dominique Strauss-Kahn looks like a good possibility.
- Wasn't he involved in some financial scandal some time back?
- No, that was not a problem. He was cleared of that charge. But he has more of a problem with women.
- A problem with women? I don't care about that. It does not matter.
- Well, he is said to be quite "heavy" ("lourd").
- [raising my voice slightly] I don't want to hear about it. I don't care about his extramarital affairs, however numerous. All I care about is whether he could be a good president, and, for that, financial scandals are relevant but not his private life."
Faced with my peremptory tone, my friend (who had met DSK once or twice, and might, perhaps, have had more to say) fell silent and I felt smug in my gossip-quenching moral superiority.

Now I wonder how many sexual aggressions go unreported because of all the people who share my attitude.

Rejecting journal submissions

I am getting tired of rejecting submissions to SIAM Journal of Computing. I keep getting referee reports along the lines of "interesting work, but not quite up to the very high standards of SiComp". What does that mean? It's not like a conference, where we simultaneously see all the submissions and can easily put them side by side and try to see which ones we like better. Instead, it's some kind of absolute threshold that apparently exists in people's heads. Because the mandates of SiComp specify that the journal must be extremely selective, I have been following referees' advice and rejecting papers that are fine papers albeit clearly not contenders for best paper awards at STOC or FOCS. But I'm not sure I believe in those hypothetical thresholds.

When I worked for Algorithmica, I normally did not accept a submission unless there was at least one referee who stated with confidence: "this is a clear accept". But for SIAM, hardly anyone seems to be willing to be so affirmative. The journal is supposed to be for the "most significant work taking place", and that is supposed to translate into "significantly more selective than STOC/FOCS/SODA", but it's depressing to reject papers that are clearly worth publishing somewhere.

So, I am looking for more objective criteria. For example, between the time when the result appeared on arxiv or at a conference, and the time when it was submitted to the journal, has the paper been read? Is the result known by people in the field? If so, then it's a sign of impact and maybe that should be compelling evidence to accept the paper. Could I ask referees to compare the paper to similar results previously published in SiComp or in JACM? That would be extra work for them. Could we request authors to provide a short list of comparable papers previously published there? Then at least I would have a benchmark and would not be working in that murky area where the "good, but not good enough" assessments sound so arbitrary.

Equality

«C'est sûr que la justice américaine est beaucoup plus violente, estime aussi Eva Joly. Ils ne font pas la différence entre le directeur du FMI et n'importe quel autre suspect. C'est l'idée de l'égalité des droits».

Translation: "Clearly, the US justice is much more violent than in France. They do not make a difference between the IMF chief and any other suspect. That's their idea of equal rights." -- French former judge Eva Joly, now a politician serving on the European parliament, commenting on the photos of a handcuffed Strauss-Kahn.

I am shocked that she is shocked that the US justice does not make a difference between criminal suspects according to their status in society. That's one potential presidential candidate who, after that comment, can be sure of not getting my vote.

Israel and France, sister countries

Israel: the former president Katsav is in prison has been sentenced to prison for rape.
France: the former future presidential candidate Strauss-Kahn is being charged with attempted rape.

One main difference is that the Israeli justice was on the first case, but it is the US justice that is on the second case. I am having grave doubts about the French justice system's treatment of public figures.

How to write programs

I have spent much of this week proofreading the programming assignments for my Fall course on introduction to programming. The texts contain many recommendations about what to put in but no recommendation on what not to put in, and they themselves are often rather wordy. I trimmed the texts, starting by removing 90% of the introductory paragraphs that give the broad context. When a student reads an assignment, his primary worry is to see what he has to do, not how the problem fits into some area of broader interest, so a sentence or two is sufficient.

In one lecture, I give a "design recipe" to design programs:
1. Define the data and provide concrete examples.
2. Define the procedure’s type signature and call structure.
3. Write a contract for the procedure and provide some test cases.
4. Write the procedure (in code).
5. Run your program on your test cases.

This year I think I'm going to add a step.
6. Clean-up your program - remove extraneous lines, consider removing helper procedures that are only called once, consider replacing nested "if" conditions by a list of cases, shorten or lengthen variable names, etc.

Or perhaps I could simply suggest:
6. Delete everything and do steps 1-5 over.
Isn't that what many good writers do? I am sure that regardless of the care with which the programmer has designed it, a program would be much better and much more elegant the second time.

The worst commercial web site

The French train company SNCF has one of the worst web sites I have ever seen. I usually go to that site to try to buy a train ticket, but it is exceedingly difficult. The big thing that occupied much of the screen this weekend on their web site: the news that SNCF sponsors the Winter Olympic games in the Alps for 2018. That's typical of the kind of information with which SNCF clutters their front page: irrelevant for 99.99% of the people accessing that web page.

I spent about one hour trying unsuccessfully to buy a ticket to go to Chamonix from Paris in August, taking a night train on the way there and a TGV on the way back. I finally determined, through trial and error, that August must be too far off for the night train system (but not for the TGV system). I will now try to buy my ticket on the phone, assuming that customer help replies to my mail asking for a phone number that can be called from abroad. I run into that problem every summer. My solution, when I am in France, is usually to physically go to the nearest train station and ask an actual physical person to help me, after standing in line for half an hour.

How come airlines and travel agents planning air travel have such convenient, well-designed websites, yet years after year the SNCF website remains just as bad as ever? Maybe the web designers are secretly trying to torpedoe their online information and reservation systems, so as to preserve employment by forcing customers to interact with SNCF employees in the real physical world. There is money to be made by someone who would build a website on top of sncf.fr, navigating the sncf website in such a way that its intricacies are transparent for the end user!

Update: no response to my email (the website promised an answer within 2 days, and it's been 6 days.) Friends in France went to the train station to asked for a phone number to call from abroad, and gave me the response: a number that only leads to an error message when called from here. French online travel companies sell tickets for flying, renting cars, hotels, tourism, but no train tickets. With this kind of marketing, I foresee a bleak future for SNCF.

The end of tenure

There's an article in "The Nation" about the inexorable dwindling, and perhaps eventual near-disappearance, of tenured jobs in academia.

A friend of mine, who teaches music in high school in Providence, has been waiting for a couple of months to hear whether she is fired for good or being rehired. Every year the Providence school district sends teachers dismissals notices and then hires them back a few months later once the budget is figured out, she told me. She is in her late twenties and takes it philosophically, not having known a society with secure jobs. (Incidentally, next year, if she is rehired, she will be working longer hours: the schoolday will end at 4pm instead of 2:50pm.)

To me, that is mind-boggling. All the people in my extended family who were not farmers worked their whole lives in secure jobs. Those who, starting in the late 19th century, were teachers or professors, saw it primarily as a vocation. But how does one nurture a vocation in an environment in which every year your employment might be terminated for budget reasons? The workplace model that is fast emerging does not seem to give any value to loyalty. What then is the point of being salaried? Better be a self-entrepreneur. If that is how they are going to be treated, maybe my friend should get together with a few like-minded teachers, and they should just create their own school.

I found a few articles about it in the news:

Shortly after Mayor Angel Taveras took office, amid what he described as a budget catastrophe, 1,934 public school teachers in Providence were fired.
The mayor and school board said they sent the dismissal notices on Feb. 25 to meet the March 1 deadline imposed by the state's Teacher Tenure Act, which sets legal conditions for the dismissal of teachers based upon economic exigency. Taveras and co-plaintiff Thomas Brady, the school superintendent, say that though they fired the teachers they intended to hire most of them back after studying the city's financial situation.

Friday, 25 Feb 2011, 1:23 PM EST
When asked Friday morning about the four-to-three vote, Taveras said the move was necessary as the city and school district look to close a multi-million dollar budget gap. "What we tried to do was create the maximum amount of flexibility, so we could make informed decisions and do it right," Taveras said. "We have to balance our budget. We have to educate our kids. We're going to do both." It's not unusual each spring for a number of teachers to receive layoff notices, only to be recalled a few months later once the budget is set. This difference this time is all of the teachers have been fired, not laid off. With layoffs, teachers are asked back based on seniority. However with terminations, the school district has more power to decide who will stay and who will go.

Tuesday, 03 May 2011, 10:26 PM EDT, PROVIDENCE, R.I.
The Providence school board has voted to immediately rehire 1,445 public school teachers. More than 1,900 were terminated in February to help balance the budget. Under the rehire plan, teacher seniority is no more. School principals will decide the teachers' duties inside the school.

Looking for a random bit

It is natural to look around us and quickly spot number patterns -- numbers or sequences that are surely not there by chance -- even when we are just making up the pattern almost in spite of ourselves. But how do you come up with a random number?

I was wondering about that driving home last night. Imagine you're having a nightmare, being chased down an alley, and you have to make a split decision whether to turn right or left, so that the ennemy chasing you won't be able to guess. Flip a coin - but what if you don't have a coin? How do you quickly make up a random decision?

As I was driving, I looked around me for features that would help me find a random number. I would have been happy with just one small random bit. Street lights, signs, speed limits, curves of the road. Branches of tall, dark trees. Gas stations. Dark sky. My cell phone was dead, and neither my car clock nor my car radio work any more. There was no random bit in sight.

If I had been hiking in a mountain, I could have given myself a goal some distance away, then counted my steps mod 2; however that would not have been really random, because, as I got close to the goal, I could have shortened or lengthened my steps in spite of my efforts for objectivity, and ended up with a number that would have been biased in some way. I am Eve, and the random bit must be protected against my malicious attempts to influence the result!

I could just come up with a number, 0 or 1, but how do I know it's random?

I could take my pulse -- how many heart beats before I get to the light? -- mod 2, except that there is always a slight uncertainty in that counting; plus, I was driving.

Finally I found an approximate solution: count, mod 2, the number of cars coming the other way, from that point on until I got home. That almost worked, except that one car came out of an intersection and turned into my street as I was just driving by, so I (Eve) had to make a subjective choice whether or not to include it; so I could have manipulated the final result in that way; but I decided it should be included and did not change my mind later.

This train of thoughts affected my driving -- it's not unusual. In the present case, when I got to the turn into my street, I sped up to go across the intersection quickly, so that no other car could come by while I was turning and present me with another subjective borderline case. I got lucky, and the intersection stayed empty while I was turning; and when I got home, my number was 33. Mod 2, that's a 1. Finally, I found a pretty good random bit!

Did I miss something obvious, I wonder? It seemed ludicrously difficult.

We are wired to find patterns, but it is much harder to spot randomness.

"Counting and waiting are the same"

That's what Joseph Hellerstein said today during his talk at Brown.

While I wait for the bus, I can engage my neighbors if there are any people around me; I can watch the trees, the birds, the traffic; I can turn inwards and focus on a problem I am currently working on. Or I can count while I wait.

Numbers are our friends.

When I was a kid, I used to have high blood pressure whenever the school nurse took my blood pressure. Waiting for her to measure it made me nervous and raised the pressure. But one day I found the secret to low blood pressure: counting. Counting keeps my blood pressure down.

When I am bored, or stressed, or at the dentist's, I count. Which numbers are prime? What are their divisors? Running the Eratosthenes sieve in my head passes the time pleasantly. Numbers are comfortingly familiar. They have a calming effect.

I can also count what I see while waiting. What fraction of the cars passing me have a passenger? How many SUV's? Do the license plates exhibit any discernible patterns? Counting helps the world make sense even when it doesn't.

How to motivate PhD students

Andy Yao was my first research mentor, when I was a visiting student in Princeton. After he had given me an open problem and we discussed it for a couple of weeks, he formulated an intermediate conjecture. If we could prove it, it would be a step forward. If we found a counter-example, it would give us new insight on the hidden difficulties.

Then he said: "Let's take a bet. Let's both try to resolve this question before we meet again next week, and let the stake of the bet be a dinner".

I couldn't pass up such a challenge, of course. I worked on the question intensively until I had solved it, a couple of days later. It made me so happy! I could barely contain my excitement. Later that day I saw Andy Yao at a seminar that we were both attending, and, unable to wait until the end of the talk, I leaned towards him and whispered with a big smile: "I solved it!" - and then, a little anxiously: "How about you, did you solve it?" No, he had not solved it. He said he was looking forward to hearing my solution during our next meeting.

And so, a few days later, we went (along with Kai Li) to a very good Chinese restaurant on Route 1 for dinner. Andy ordered lots of food, and, in particular, some fresh lobster. But I had never had that before and didn't know how to eat it properly, so I politely declined the lobster, contenting myself with the other dishes. In my memory, the dinner was delicious.

Now I see that that bet was an obvious ploy to get the student interested. I fell for it completely! What a great idea.

How to write papers: a reader-as-machine perspective

The reader has short attention span and little memory. Assuming that the reader is someone who wants to check correctness of a paper, how does the writer take into account the reader's limited capabilities? Imagine the reader is a machine with limited resources in time and memory, and that is interruptible.

Dealing with the short attention span:
(1) Each piece of information in the paper should be neatly packaged in about half a page, so that the reader can take a break after absorbing the material in that half-page.
(2) The most interesting result should come first. Or, rather, the paper should start with a shortest path to the main idea. This way, if the reader gives up after a few pages, it maximizes the chance that he will get to the main point of the paper.
(3) Side issues should be raised in comments or remarks separated from the proof of the main result; that is the presentation chosen, for example, in the Jerrum-Sinclair 1989 paper on computing the permanent.

Dealing with lack of memory:
(1) State lemmas as close as possible to the place where they are used; state definitions as close as possible to the place where they are used.
(2) A definition or a notation takes room in the reader's memory: minimize that, wisely taking into account time-space tradeoff:
"Let x denote blah blah blah ... Using x,... because of x..."
versus
"Using blah blah blah, ... because of blah blah blah".
Is it preferable that the reader first parse blah blah blah, then have to store it in memory, or that he have to parse blah blah blah every time he encounters it?
(3) Order lemmas, facts and theorems so as to minimize the width of the resulting dependency graph. In that way, the reader only has to remember a few statements at a time.