Sunday, March 27, 2011

Wigderson against Pharisaism

Avi Wigderson taught a mini-course on expanders in Paris last week. I spent some time there learning about expanders, and some time learning about teaching.

When I present an algorithm or proof in a talk, in order to convey the main ideas, I sometimes ignore side concerns, which sometimes makes me take liberties with correctness stricto sensu. Avi takes that approach and carries it to an extreme: when briefly presenting a research direction, he may choose to briefly outline the prettiest algorithm, while briefly citing only the most important paper on the subject, even if there is a mismatch between the result outlined and the paper cited! I would not dare do that (at least not on purpose), for fear of catching hell from authors. But it is morally doing the right thing: giving a pointer to the one paper interested students ought to look at, while attracting them with hints of the most elegant results.

It's sacrificing accuracy in the details, so as to better get the essential ideas across. In fact, it's also sacrificing some accuracy to beauty. It's an anti-Pharisee stance: Pharisees, I am told, were so obsessed with rules and with following every detail of every ritual in exactly the right way, that those regulations obscured the overall purpose of their religious practice.

Friday, March 25, 2011

"P < > NP is a fact of nature"

That was the message from Avi Wigderson's pop talk on Wednesday in Paris.

Consequently, an open question: how does nature know how to efficiently fold proteins? Is it that our theoretical models are wrong (so that the problem is not really NP-hard)? Or is it that there is additional structure that gives it structure that makes it amenable? Either way, the answer would be interesting.

In Avi's world "interesting" is a word loaded with meaning. He does not employ it to mean a polite lack of dissent, but to mean that something like "revealing a deeper truth".

Wednesday, March 23, 2011

Philippe Flajolet

Claude Puech was my PhD advisor, and his own PhD advisor was Philippe Flajolet, so I am a proud to count myself as an academic grandchild of Philippe. In 2007, he gave a great invited talk at the SODA conference in New Orleans, with his usual charisma, enthusiasm and clarity, and we had a "French-speaking lunch" in the New Orleans French quarter, together with a small group of other francophone attendees. Our research tastes are somewhat different, but I have always looked up to him with great admiration.

Today I hear some sad news. http://en.wikipedia.org/wiki/Philippe_Flajolet

Monday, March 21, 2011

Trust and Authorities

Rather than hearing only a few voices from traditional media, I much prefer the cacophony of internet articles, news and reports about the Fukushima nuclear power plant accident, yet the array of more or less informed opinions is bewildering. It would be nice to have a quick way to recognize authorities on an emerging topic. Here is what I have noticed. Some media:

- are not up to date and keep reports that are more than 24 hours behind
- do not date the events they report ("This morning" quickly gets old as a way to date events!)
- do not give quantitative information, confuse legal limit with safe limit, confuse or perhaps intentionally try to confuse short-term risk with long-term risk, confuse individual risk with a population's risk (if an individual now had an additional 3% risk of dying from cancer, that might be acceptable for some individuals under some circumstances; if the Tokyo agglomeration was going to have an excess 1 million deaths from cancer, that would be a major, major public health issue.)
- confuse units (micro versys milli), confuse reactors, confuse reactors with plants, confuse core with spent-fuel pools, confuse containment vessel with outer shell, confuse kilometers with miles, etc.
- do not specify where measurements were taken ("at the plant": 1 km from reactor, at reactor, inside reactor? That's different by orders of magnitude.)
- focus on the future at the expense of description of the present
- when asked to make a prediction, only give a best case description, or only give a worst-case description
- do not put their quantitative information in context. What is safe? How safe is safe?

I found that interviews of scientists and experts do not actually yield a more level-headed assessment. The main effect seems to be to give more confidence to whatever assessment the newspaper is aiming for, but the resulting article is more biased than it would otherwise be. Just because scientists are able to avoid basic mistakes does not mean that they do not emphasize only the information that goes the way they want it to go! On the contrary, I am afraid that they come off looking not very good. One can definitely not consider them to be trustworthy authorities.

I found that the wikipedia website on the nuclear accident was one of the best sources of information. Sometimes a useful information appeared and later disappeared, but not often. That's a little bit mysterious: how can something as loosely controled as wikipedia give such reliable information?

Tuesday, March 15, 2011

UPDATED- “The past was erased, the erasure was forgotten, the lie became truth.” - Trust the experts!

UPDATE- Apparently Dr. Josef Oehmen, an MIT specialist in risk management, is the author of the essay “Why I’m not worried about Japan’s nuclear reactors”. It was an email that he sent to his family in Japan and that went viral.

That changes a lot of things. A private message to try to reassure one's family is very different from a report posted for the general public. Even though the writer is being reassuring, he could be having reservations that he preferred not to voice: "The large amount of cooling water that has been used is sufficient to take up that heat [in petto: at least, I hope so]. ... Boric acid is "liquid control rod". Whatever decay is still going on, the Boron will capture the neutrons [in petto: I hope so!] "...

Read more: http://www.businessinsider.com/japan-reactors-pose-no-risk-2011-3#ixzz1GiJ7unMl

Isn't it ironical that I have to correct a post in which I complained about other people's updates to their own posts!

-------------------------- Original post ----------------------------

On the day before yesterday, in a comment, Neal linked to a detailed guest post there
from a nuclear expert presenting the technology behind the design of the Fukushima muclear power plant and explaining that there is no reason to worry.

Today the post has been moved to an MIT nuclear physics website (were the original contributors from there? I did not pay attention), but it's been vastly edited. Now it is purely factual, the claim that the containment vessels are impossible to damage has disappeared, and the confident assessment of an evolution where everything is under control has totally disappeared. The rewriting of history has started!

Suddenly I am sorely missing our old-fashioned paper media. The shameless removal of erroneous expert predictions that I am witnessing here is reminiscent of 1984. The proper thing to do would have been to leave in place the piece that was already there, while adding an update. Perhaps, cross out some sentences so that the reader can see what statements made on day x are rescinded in day x+2. How else can we make accountable the scientists who inform public opinion and who serve as advisors for political decisions? How else can we restore the credibility of scientists among the general public?

------------------------

Meanwhile the journalists reports of radioactive measurements are showing some confusion between microsieverts and millisierverts. Not in any intentional way, I think. I do not see a pattern of deception but genuine mistakes.

Monday, March 14, 2011

More on rare events

AP Paris -- "“Europe has to wake up from its Sleeping Beauty slumber” about nuclear safety, Austria’s Environment Minister Nikolaus Berlakovich told reporters in Brussels. He suggested an EU-wide stress test for nuclear plants, much like European banks have been tested for their ability to cope with financial shocks. Yet some experts and officials say those fears are overblown, given the exceptional nature of Japan’s earthquake and ensuing tsunami. The Japanese blasts may slow the push for more nuclear plants, but appear unlikely to stop it, given the world’s fast-growing energy needs."

"exceptional" = roughly one-in-twenty-five odds, in the present case, according to historical records of natural disasters in Japan.
How many once-a-millenium events are dismissed in various countries when designing nuclear power plants, because of their "exceptional" nature?

What Yuval Peres was telling me today: that people cannot distinguish between odds of one-in-one-hundred and of one-in-one-million. That's why there is every reason to be worried about current safety measures everywhere. The last sentence of the AP article reminds me of a XIVth century French proverb: "Il n'est pire sourd que celui qui ne veut pas entendre" [No one is deaf like the one who does not want to hear].

--------------------

When I go into the mountains with my son, sometimes we go to exposed locations. At this point he is more nimble than me and I cannot protect him physically; but I always remind him: "Here, you must not fall. Don't go there if you're not sure you'll make it. Don't go, even if you think that the odds are 9 in 10 that you'll be fine. Even 99 out of 100 is not good enough, since that would mean that you would fall after we've gone mountaineering for a hundred times or so. In this instance (say, walking on top of a cliff with a tremendous drop all but guaranteeing death in case of a fall, for example), I don't want you to fall, not even once." --- of course the safer option would be not to go mountaineering at all, but life would be pretty dull if we could not do the things that bring us the most joy; so there's some amount of risk that we're willing to take. I know that there is a risk, I hope that it is minuscule, and I trust that my son knows how to gauge it. Mountain guides: that's one profession where they have to know how to assess risk if they want to grow old.

Meanwhile, a few proponents of nuclear energy are admiringly drawing attention to the 50 Japanese plants that did not cause any trouble in spite of the earthquake and tsunami. That argument does not inspire trust but misgivings, raising doubts about the competence of those "experts" in risk assessment. Maybe nuclear power companies should recruit mountain guides for consulting!

Sunday, March 13, 2011

Assessing the risk of rare events

Some time ago I had a discussion with, I think, a probabilist (maybe it was Yuval Peres), who advanced the opinion that humans are really bad at understanding the odds of rare events. Even probabilists don't really understand rare events, he said.

I saw a report of an interview of a Japanese professor saying that Friday's events were "literally" a "once a millenium" event: in 869 there was an earthquake of this scale, with a tsunami that went 3 miles inland. At first, once a millenium sounds pretty low... until you realize that, for a plant with a lifetime of 40 years, it's an unacceptable 1-in-25 odds!

-------------

Coincidentally, on Thursday evening I happened to be chatting with a mathematician friend about the Japanese's amazing ability for reconstruction from scratch; the specific topic of our conversation was their rise as international mathematicians in every major area of mathematics since WW2.

-------------

At Notre-Dame de Paris cathedral, there was a Mass for the people of Japan. Standing room only. Many Japanese, including the ambassador of Japan in France. As it happened, the day's first reading was on Adam and Eve's banishment from Eden, so the archbishop talked about the meaning of death; but I found it academic more than sympathetic. Anecdotically, in the procession at the end, I saw Sarkozy walk right by me, just a couple of yards away!
Here is what some Christians have been using to pray this weekend:
The waves of death rose about me;
the torrents of destruction assailed me;
the snares of the grave surrounded me;
the traps of death confronted me.
The earth reeled and rocked;
The mountains were shaken to their base.
The bed of the ocean was revealed;
The foundations of the world were laid bare.
From on high he reached me and seized me;
He drew me forth from the mighty waters.
From Psalm 18
Psalms are amazing. Thousands of years old, yet there's always one appropriate for every circumstance!

-------------------------------

SODA will be in Japan in 2012.

Friday, March 11, 2011

The Arora-Barak-Steurer paper on unique games

I am finally slogging through the Arora-Barak-Steurer paper on a subexponential algorithm for unique games, almost a year after it first came out. I have written a summary of the algorithm and the lemmas that state the structural properties achieved at each step of the algorithm (no proofs). It's not that hard, after all. Teaching it, I think, would require a few lectures:
- one lecture to present the problem, the conjecture, and put it in context (why people care).
- one lecture on expanders (for the preprocessing step)
- one or two lectures on spectral graph methods, proving Cheeger's inequality
- two lectures to present the algorithm and analysis in the Arora-Barak-Steurer paper, including the proof of the variant of Cheeger's inequality.

Wednesday, March 9, 2011

Gaps in my knowledge

If I was starting over with my education... here are some courses I wish I had had when I was a student:

- Probability and random walks, "a la" Yuval Peres
- Spectral graph theory.

Friday, March 4, 2011

Dagstuhl Thursday night

On Thursday night, in the cheese room, we had an informal discussion on the future of scheduling. A list of open-ended questions had been prepared, several people had been told in advance to think about it, and I moderated the discussion in the same way as I do in the classroom when I teach. Much of the discussion was about the relation between theory and applications. Some directions that were proposed: robust scheduling, stochastic scheduling, scheduling a sequence of similar instances, behavioral scheduling, inapproximability, etc. Many other things were brought up. Miraculously, someone - Alexander Souza - came to me afterwards and, without being prompted, volunteered to write up a report of the discussion! He instantaneously became my hero of the day.

Talking about applications of theoretical work, several people said they had heard that Niv Buchbinder had designed some algorithm that had had practical impact while he was a postdoc at MSR; but Niv adamantly refused to acknowledge the possibility that he might have done something actually useful. He's funny! It's a measure of how informal the atmosphere was that people, instead of trying to show how important their work was, may have downplayed its importance.

The last question was: what drives you to work on scheduling problems? Baruch Schieber talked eloquently about the gratification that comes from doing work that is useful for others. David Johnson mentioned the pleasure of working on problems that one can explain to Beotians. Fritz mentioned the value of our results, as measured by society's feedback. Kirk, down to earth as always, said that it's good to work on topics for which you can get funding. I brought up the importance of beauty, but Neal Young said, essentially, that beauty is in the eye of the beholder.

But doesn't our work have intrinsic value? If I found a solution to, say, the k-server problem, it would make me very happy and I would think that the solution has value even if no one else cared or knew about it.