Saturday, June 11, 2011

Fukushima three months later: the sorcerer's apprentice

Three months after the nuclear power plant accident at Fukushima, how far is Japan along the plan to recovery?

At the plant, the situation is "stable" in the sense that there is no more risk of sudden degradation than there was a month ago. The workers may be becoming worn out, the rain season and associated risk of typhoon are worrisome, the work is hampered by the accumulation of radiation in every object on site, but there is some progress. For example, containers for radioactive water are being brought in; measurement instruments have been set up, humans and robots have entered the buildings a couple of times for a few minutes. Information is little by little coming out to reveal that the catastrophic events three months ago were much worse than first assessed, so the present looks better in comparison. There is no clear plan forward, so in a way this is like a "new frontier" for science.

In the region, the situation is slowly degrading as radioactivity is spreading in air, water, soil, and food, in a spotty, haphazard manner. However the long term effects of non-acute radioactivity are not well known. There are almost no casualties at present, and everyone is in the dark regarding the potential casualties in 20 or 30 years (the number of deaths attributable to Chernobyl varies from 64 to 985000, depending on what you read). The media are split between systematic under-reporting of the seriousness of the situation, systematic fear-mongering, and plain and simple silence as they have moved on to other topics.

Wondering about nuclear power, I am irresistibly reminded of the scene in Fantasia where Mickey Mouse, apprentice magician, uses magic brooms to do his chores for him, as an illustration of the dangers of power over wisdom.

Raw data: http://atmc.jp/plant/rad/?n=1
News aggregator: http://enenews.com
Japanese blog: http://ex-skf.blogspot.com

UPDATE: Italians have voted against developing nuclear power again in Italy. Their vote, by referendum, was quasi-unanimous: 94.05% of the votes!

Wednesday, June 8, 2011

What experience teaches you

Hemon in The New Yorker:

"When he was young, like me, he [Macalister] said, he had thought that all the great writers knew something he didn’t. He’d thought that if he read their books he would learn something, get better. He’d thought that he would acquire what those writers had: the wisdom, the truth, the wholeness, the real shit. He had been burning to write, hungry for that knowledge. But now he knew that that hunger was vainglorious; now he knew that writers knew nothing, really—most of them were just faking it. He knew nothing. There was nothing to know, nothing on the other side. There was no walker, no path, just walking. This was it, whoever you were, wherever you were, whatever it was, and you had to make peace with that fact."

Read more http://www.newyorker.com/fiction/features/2008/09/22/080922fi_fiction_hemon#ixzz1OdPdoG9f

Tuesday, June 7, 2011

Faster program committees

Why not have the following procedure to select papers?

Day 1: submission deadline
Day 1 to day 3: assignment of submitted papers to PC members
Day 4 to day 9: physical PC meeting at some location such as Dagstuhl or NSF to read, discuss, and select the papers
Day 10: list of accepted papers is made public.

Pros:
The work for PC members would be concentrated in a single week, more efficient.
Authors would get results almost immediately.
There would be much more interaction between PC members, which would be a much more efficient way to read, learn and form an opinion about submissions.
There would be a clearer distinction between conference and journal evaluation.
The total amount of work per PC member would be reduced.

Cons:
There wouldn't be time to get outside expertise except for emergencies.
The type-A PC members might dominate the decisions.
PC members would be spending that time away from their families.
Would any conference center be willing to let a committee use their space for that?

Monday, June 6, 2011

The easiest primal-dual algorithm

What is a good algorithm to teach the primal-dual technique for the design of approximation algorithms? One simple algorithm is in Charikar and Panigrahy's 2001 paper on clustering. This particular solution contains all the basic ideas of primal-dual algorithms, but none of the technical issues that come up in most applications. It's like a baby version of the facility location primal dual algorithm.

The input is a finite metric space and a cost f for each cluster opening. The output is a collection of balls (clusters), each ball B(i,r) centered at some point i and of some radius r, so as to cover all points. The value to minimize is f times the number of clusters, plus the sum of cluster radii.

First they design a linear programming relaxation, where x(i,r) indicates whether the ball B(i,r) is in the solution, and where there is one constraint for each point j, indicating that there has to be at least one ball B(i,r) selected for some r and some i within distance r of j. Then they write the dual. The dual linear program simply has one variable a(j) for each point j, and one constraint for each ball B(i,r), stating that the a(j)'s for j in that ball must sum to at most f+r.

The algorithm picks an arbitrary feasible dual solution that is a local maximum w.r.to changing a single coordinate a(j). In other words, the dual solution (a(j)) is such that for every j, there exists a ball B(i,r) containing j, such that the dual constraint is tight. Then, to deduce a feasible primal solution, let T be the set of such balls B(i,r). The algorithm greedily goes through all balls of T by order of non-increasing radius, to construct a subset S of disjoint balls of T. Finally, the primal output solution consists of the balls B(i,3r) for each ball B(i,r) in S.

For the analysis, they first need to prove that the output is feasible, that is, that the output balls cover every j. Fix a j: it's in some ball B(i,r) of T. If that ball is not in S, it's because it intersects some ball B(i',r') that is in S, so the output contains ball B(i',3r'). By the greedy definition of S, r' is larger than r, so the ball B(i',3r') covers j.

Then they need to bound the cost of the output balls. It's at most three times the cost of the balls in S. Since the balls in S are a disjoint subset of T, the corresponding tight constraints sum to give that the cost of S is at most the sum of all a(j)'s, which is less than OPT by linear programming duality. That concludes the proof of a 3-approximation.

Sunday, June 5, 2011

Unsynchronized elevators and selfishness

My building has two elevators, each with its own call button, independent of each other. My office is on the top floor, and when I want to take the elevator, I systematically push both buttons, so as to minimize my waiting time. Then I simply go into the first elevator that makes it up to my floor, and my waiting time is the minimum of the two waiting times.

This week I got chided by my visitor for that behavior. He claimed that I was increasing everyone's waiting time, because I was making both elevators come to my floor, but one of them was just coming up for nothing. That slows things down for everyone in the building, he argued. If everyone does the same as me, it is almost as if there were twice as many people in the building as there really are, so my behavior induces dynamics that are very far from the social optimum. In other words, I am violating Kant's universal moral law: "Act only in accordance with that maxim through which you can at the same time will that it become a universal law." Instead, I am selfishly choosing my actions so that, if everyone else's actions are fixed, I am minimizing my personal waiting time.

Some remarks:
- I have been doing this for close to seven years, but never thought about it, and no one had mentioned it to me before. Are selfish choices so ingrained in the culture here in the US that we don't even think to question them?
- My visitor was from France, where there is a tradition of being socially minded (as in: people on the street tend to support strikers even if it causes them hours of delays). Are social-minded choices so ingrained in that culture that it is natural for them to first look for actions that realize the social optimum (that is, apply Kant's law)?
- It is not possible to modify the current layout and synchronize the elevator buttons because of some security reason, or so the elevator company claims. Could we modify the system to give some kind of reward to not push both buttons? For example, if pushing the button gave us a slight electric jolt, or if the buttons were slightly gooey, or if we had to swipe our card and had a daily quota of button calls...

Saturday, June 4, 2011

Why go to college? An education

I just watched the movie "An education". One question that kept coming up but never got a satisfactory answer: "Why go to college?"

The private high school teachers claimed that learning (Latin, in that case), although it was "hard and boring", was worthwhile, but I didn't see that they offered a compelling answer.

I disagree with the "boring" part. It propagates a prejudice. Learning is hard, but it is not boring. It carries in itself a lot of its reward. I could imagine the girl in the movie, or her teacher, coming up with just the right way to translate some Latin text written thousands of years ago so as to convey just the right nuances of meaning, and getting excited about it. Or the girl could be spending hours and hours working on a difficult passage with her cello, until she finally masters it, and getting thrilled by the music or by her accomplishment. The movie does not give any hint of what is good about learning, besides getting students into Oxford (and finding a husband, as was apparently the girl's father's ultimate goal for her).

Even for the other side of the girl's "education", the description was not that compelling either. She describes it as "going to restaurants and concerts" and generally going out and having fun, as though that was all that there was about the world outside the (perceived) drudgery of school and work. She could have talked about the excitement of meeting people who are older and who have more experience, more ideas, and more conversation. There was much talk of the excitement of going to Paris on a trip, but what was exciting about it? We have no idea. The couple of snapshots of Paris were just enough to indicate that she was there, but not to imply any particular kind of discovery. The aspects of physical awakening were also underplayed (although surely on purpose, in this case).

I thought the movie was going to show a conflict of values and offer some perspective on the question: "What is the point of getting an education? What is the point of going out into the real world?", but it didn't address that question except at the shallowest level.

Thursday, June 2, 2011

The job market in my state

Today someone told me happily that they had gotten a job, four hours a week of paid work -- on condition that they also do four hours a week of (unpaid) volunteer work at the same place. That's the current state of the job market in Rhode Island.

Tuesday, May 31, 2011

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.

Monday, May 30, 2011

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.

Sunday, May 29, 2011

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?