Making a half-batch of wassail is hard — without the sheer volume of liquid, the roasted/caramelized apples have a hard time floating.
Monthly Archives: December 2005
jai yun
I went to Jai Yun last night, and I have to say it was probably the best Chinese meal I’ve ever had. Unfortunately, I forgot to bring my camera and I missed a lot of the cold plates at the beginning since BART had problems and I had to run there. There are only a few tables in the place, and everyone’s dinner begins at the same time, because the chef has a fixed menu. The restaurant is prix fixe — you specify how much you’ll pay per head and they bring out dish after dish. It’s all small plates, so you get an amazing variety of food, all from around Shanghai. Afterwards the chef comes out of the kitchen and pretty much everyone applauds because the food was so damn good.
The most interesting thing about the meal was that most of the dishes were things I had never tried — abalone with eggs, this crazy grouper, tofu and celery, winter melon with ground pork, shrimp with ginko nuts, and so on. A few of the dishes were “familiar” from more American Chinese restaurants, but even these were wholly different in taste. The kung pao chicken was ridiculously spicy, but managed within that space to find a balance between the black and red pepper flavors. The orange beef thing was crispy thin slices of deep fried beef with a delicate orange flavor that just melted in your mouth.
All in all, it was a mouth-opening and wallet-emptying experience. Maybe I’ll go there again when I’m rich and famous.
medical exploitation of India
Via Krish, a story in Wired about how India is now the big site for clinical trials and drug development. Costs there are low, and as the editor of the American Journal of Bioethics noted:
Individuals who participate in Indian clinical trials usually won’t be educated. Offering $100 may be undue enticement; they may not even realize that they are being coerced.
I heard a radio program on this a few months back and tried to get my mother riled up about it, but it’s really just another strand in the rich and varied tapestry of India’s exploitation by the West/North/what-have-you.
As with most issues surrounding technology development, it boils down to an issue of pragmatics versus ethics. Pharmaceutical companies in Europe and Asia can’t find people willing to do clinical trials of their drugs in the US, even with some generous incentives. After all, who wants a placebo? On the other hand, you can get lots of volunteers for just $100 a pop in India plus paying the doctor to administer the trial, and the FDA will approve your trial. You get your drug approved, patent it, and prevent anyone in India from actually being able to afford it.
It’s not a problem specific to India either — patients in Russia are exploited in similar ways. When access to quality healthcare is limited, desperation is the primary motivating factor. Is it ethical to give a placebo in these situations? Should there be restrictions on how these studies are marketed to the public? Bioethics is going out the window in our rush for progress and refusal to shoulder the risks ourselves.
spinnerty
Check out the new website of DJ Spinnerty. One of these days I’ll get to see his show…
always be cobbling
Remember folks, hot cocoa is for cobblers. (Via Adam, of the defunct Schmonkey Report).
paper a day : the Gale-Ryser theorem
By request, today’s paper is kind of about the mathematics of paint-by-numbers puzzles. Merry Christmas, Erin.
A Simple Proof of the Gale-Ryser Theorem
Manfred Krause
The American Mathematical Monthly, Vol. 103, No. 4. (Apr., 1996), pp. 335-337.
The Gale-Ryser Theorem is one of those beautiful little gems in combinatorics. The problem is rather simple to state. Suppose you have a k by n matrix A of zeros and ones. Let r be the vector of sums along each row and c be the vector of sums along each column. The question is this : given an r and a c, when does there exist a matrix A with those row and column sums?
First off, note that r and c satisfy
since the total number of ones has to be constant. We need a few more concepts to understand the result. A partition of N is a set of positive integers r1 ≥ r2 ≥ … ≥ rk whose sum is N. It turns out that it’s sufficient to only consider r and c that are partitions (hint : start swapping rows and columns).
Given two partitions r and c of N, we say r is dominated by c if
where the summands become 0 if we exhaust the partition. As it turns out, dominance provides a partial order on the set of partitions that is particularly useful in combinatorics. The whole theory of majorization is based around the dominance order.
The last concept we need is a Ferrers board and the conjugate partition. Given a partition r of N, imagine a matrix of 0’s and 1’s that has rj 1’s in row j. This is the Ferrers matrix of the partition. The conjugate partition of r, denoted by r*, is the partition whose Ferrers matrix is the transpose of the Ferrers matrix for r.
The Gale-Ryser theorem says that a matrix A exists with row and column sums r and c if and only if r is dominated by c*.
To prove that we need the dominance relation, suppose that r is not dominated by c*. Then look for gaps in A — that is, rows in which you get a 0 and then a 1. Induction on the number of gaps proves it. If there are no gaps we have a Ferrers matrix, so we’re done. If there is a gap, you can swap two entries in a column to reduce the number of gaps.
The novelty in the paper is a new proof of the “only if” half of the statement. It’s basically an algorithm that provably constructs a matrix satisfying the row and column sums given. Clearly this matrix is not unique in general. You start with the Ferrers matrix A0 for c and do a series of swaps until the row sums equal r. Let Aj be the matrix after j swaps. The algorithm guarantees the following:
So it will eventually converge to a valid matrix.
The application to paint-by-numbers should be pretty clear. A PBN is just a 0-1 matrix of pixels. If the image in the PBN is convex, then the puzzle is kind of trivial, but you can use the theorem to decide if it's solvable. An interesting extension to work out would be a theorem or fast algorithm for deciding if a general PBN is solvable or not. If I had the time to think about this, I would. Maybe it's something to do on a rainy afternoon after my deadlines have passed.
am I a peer?
I’ve actually been invited to review a paper, which is a first for me. I guess all that stuff on peer review I’ve been reading during my procrastinating moments will actually come in use now. They’ve asked me to turn in my review in two months, which is good for me, since I have too many looming deadlines. I guess this is why publishing takes so long — reviewers take 2 months, editorial checking and decision, revisions, another round of reviewing, more revisions, and submission. It’s no wonder that in computer science they put all their energy into conferences — it keps the pace of research higher.
secularmas
As Fafnir says, “Secularists don’t decorate Christmas trees. They decorate Secularmas trees, which are big holes dug in the ground to demonstrate the absence of trees.”
paper a day : marton’s broadcast region
This is pretty heavy on the information theory I guess…
A Coding Theorem for the Discrete Memoryless Broadcast Channel
Katalin Marton
IEEE Trans. Info. Theory, 25(3), 1979
This is a short paper that had a reputation (in my mind at least) for being hard to figure out. I think after my 3rd pass through it I kind of get it. The ingredients are: strongly typical sequences and auxiliary random variables that mimic the broadcast.
Suppose you want to send two different messages to two different people. Unfortunately, you can only broadcast, so that if you send Y then one person gets X via a communication channel F(X|Y) and the other gets Z via G(Z|Y). Given F and G, how should you design a Y so that the messages are decodable by their respective recipients, and so that the number of bits in the message is maximized? If we consider data rates, what are the maximum reliable rates of communication to the two users?
It turns out that the converse to this problem is not tight in many cases. That is, the set of data rates which are achievable is smaller than the set which may be achievable. This paper expands the region of achievable rates by a little bit more than had been known before 1979.
If Rx and Rz are the rates to the two users, then Marton shows that for random variables (U, V, W) which form Markov chains (U, V, W) – Y – X and (U, V, W) – Y – Z :
Rx ≤ I(W,U ; X)
Rx ≤ I(W,V ; Z)
Rx + Rz ≤ min{ I(W ; X), I(W ; Z) } + I(U ; X | W) + I(V ; X | W) – I(U ; V | W)
The main benefit of this theorem is that before U, V, and W had to be independent, and now they can be dependent.
The interesting part of this paper is of course the code construction (plus some applications at the end to the Blackwell channel that I won’t bother with here). The sketch is as follows — generate codewords wi iid with respect to W, then U codewords iid with P(u | wi), and V codewords iid with P(v | wi). Then you look at triples of (u, v, w) that are strongly typical, and for each one choose a random Y that is strongly typical conditioned on (u, v, w). Then the decoding is via strong typicality.
The details of the proof are interesting, but what I think it’s a great example of is how the pre-encoding can mimic broadcasting (W sends to U and V) and that this mimickry can be brought over to the channels at hand and is provably achievable. Marton writes that she thinks the novelty lies in the case when W is deterministic. In any case, it was an interesting read, and has given me a few more ideas to think about with respect to my own research.
my new title
Many many hours and one expensive parking ticket later, I finally finished.
You may now call my Master Anand.
That is all.
An Ergodic Walk 