Corruption of the scientific process

This is an amusing and disturbing description of a scientist trying to get a journal to publish his reply to a paper erroneously refuting his life's work.

The author refrains from mentioning his field, but it isn't the first time a story like this has come to my attention (see, e.g., Steve McIntyre's various experiences in the world of climate research at www.climateaudit.org).

Here's another amusing/disturbing story from the top ranks of the climate world.

Astounding. Compared with the commonly held myth that "peer reviewed" means "case proven", this sort of thing can only be doing real damage to both the scientific process and the wider public perception of science.

Addendum: I should qualify that last remark that by explaining that I am, and have been, a reviewer for several top tier computer science conferences for about a decade. My job as a reviewer is to decide (a) whether a paper is original, (b) whether it defends its thesis, (c) whether it has provided satisfactory answers to the reader's questions, (d) whether it is readable, and (e) whether it explains the research well enough for the work to be reproduced with reasonable effort by any other member of the community. If a paper fails this last hurdle then it is essentially a set of claims lacking adequate support. Now, even if I recommend a paper for publication, that does not mean I accept its conclusions as truth. Rather, I am suggesting that the work is of sufficient value that it may be worth replication. Replication, not publication, is the gold standard of science.

The Coloured Stamps Problem

This is a trickier variant of the Coloured Hats problem, due to Raymond Smullyan.

This time a mischievous student has placed two stamps on the foreheads of each of three sleeping philosophers, X, Y, and Z. The student then wakes them and explains that the pairs of stamps were drawn randomly from a set of four green and four red stamps (the remaining pair of stamps being hidden). He proceeds to ask each of the philosophers in turn whether they know which colour stamps are on their forehead:
X: no.
Y: no.
Z: no.
Then the student goes around the group again asking the same question:
X: no.
Y: yes!
How did Y solve the problem?

Solution

Let us write rr, gg, and rg for the three possible stamp combinations (red/red, green/green, and red/green). We will write X is rr to denote X having red/red on his forehead, and so on.

We can immediately reject the X is gg and Z is gg case, since Y would know immediately that he is rr (but doesn't). Similarly for X is rr and Z is rr.

So Y starts by assuming Y is rr.

We can eliminate all possibilities where X is rr (since Z would immediately deduce that he is gg) or Z is rr (since X would immediately deduce he is gg).

This leaves the possibilities

• X is gg and Z is rg, or
  
• X is rg and Z is gg, or
  
• X is rg and Z is rg.

If X is gg, then Z knows he is not rr (since X would know he is gg, but he doesn't), and that he is not gg (since Y would know he is rr, but he doesn't), hence Z would know that Z is rg. He doesn't, hence X cannot be gg.

If Z is gg, then X would know on the second round that he was rg. He doesn't, hence Z cannot be gg.

The remaining possibility is X is rg and Z is rg. In this case, after the first round, X would know he must be rg, but he doesn't. Therefore X cannot be rg.

Y therefore concludes that he cannot be rr.

By symmetry, Y also concludes that he cannot be gg.

Therefore, Y knows he must be rg.

The Coloured Hats Problem

I've been enjoying Raymond Smullyan's "Satan, Cantor, and Infinity", trying to solve all the problems therein. This one is cute:

The Coloured Hats Problem

A student has placed a green hat on the head of each of three sleeping philosophers, X, Y, and Z. He wakes them up and explains that each of them is wearing a red hat or a green hat, but of course none can see what they themselves are wearing. The student first asks the philosophers to raise their hand if they can see at least one green hat. Of course, all three raise their hands. The student then tells them to put their hands down if they know the colour of their own hat. After a few seconds thought, the smartest philosopher puts her hand down. How did she solve the problem?

Solution

Let's assume the smart philosopher is X. X reasons that if X had a red hat then one of the other philosophers, Y say, would be able to immediately deduce that their hat must be green because Z raised his hand (Z sees at least one green hat). Since this has not happened, X concludes that her hat cannot be red and therefore must be green.

The Stony Brook Algorithm Repository

I've just stumbled across the Stony Brook Algorithm Repository. Could be handy.

Tents puzzle google gadget

I finally got around to setting up my tents puzzle as a Google gadget. You can use the this link to add it to your iGoogle page.

I used the Google gadget editor to handle things. It's quirky, but usable, although I really wouldn't want to develop anything serious in it to start with. For a start, it doesn't work in Chrome at present, nor does the preview window seem to display things like tabs or dynamic height control. I'm sure all these things will be fixed before too long.

Watchmen

Brilliant, brilliant film.

Fillomino puzzles

I work on the G12 constraint programming system. I've been putting together models for the forthcoming MiniZinc Constraint Solver Challenge; one of the most interesting was finding a model for fillomino puzzles. A fillomino puzzle looks like this (which I took from Vegard Hanssens' page to which I just linked):

1 . . . 1
. . . 1 .
2 4 . . .
1 . 2 1 .
3 . 1 . 2

The goal is to complete the grid by dividing it into "regions" (where a region is a maximally contiguous set of cells connected by their edges) where each cell in a region is labelled with the size of the region. Thus, a 1-region will contain a single 1 and have no bordering 1-regions; a 2-region will consist of two neighbouring cells containing 2s and have no bordering 2-regions; and so forth. Some regions may start with more than one cell filled in; some may have no clues filled in at the start. The solution to the problem above is

1 4 2 2 1
2 4 4 1 4
2 4 2 4 4
1 3 2 1 4
3 3 1 2 2

This is a surprisingly difficult puzzle to model due to the region contiguity constraints. My solution works as follows:

• each cell is a potential "root" of a region (and each region has a single root);
• neighbouring cells are either in the same region (and hence have the same number) or are in different regions (which must have different numbers);
• each cell has a time step at which we label it (region roots are labelled at step 1, all other cells are labelled later);
• any cell labelled at step t > 1 must be part of the region of a neighbouring cell labelled at step t;
• each region must be labelled with the size of the region.
  

The time step labelling and the unique roots constraints ensure that regions grow contiguously. The problem with this model is that it is hard to get decent propagation out of it (propagation is where the search tree is pruned as far as possible after each choice point). A human solver will recognise that there's no point trying to fill in a region of four cells with 5s; I have not yet found any good way of describing this information in the model.

Google Wave

I watched the Google Wave presentation over the weekend. Wave is an open collaborative editing system that integrates e-mail, blogging, wikies, photo albums, various kinds of polling and data collection, under a single, simple abstraction. If it is as easy to use in practice as the demo looks, my guess is that it will radically change how people interact over the internet. Very, very cool.

I've just come across ASCIIMathML. It's superb!

`e^(ipi)=-1`

`mu = E(X) = sum_x.x*P(X = x)`

`sigma^2 = V(X) = sum_x.(x-E(X))^2`

Update: there appears to be a bug in Chrome's rendering of these formulae in that the first `x`s should appear under the `sum` signs, not after them. I've added some '.'s to make the meaning clearer for Chrome users.