even birds have their rebellious phase

An article just came out that says

Young canaries happily learn songs that sound nothing like their species, but they revert to a strict canary-like melody as they mature, Science reports.

I guess canaries eventually grow up and settle down to become just like their parents. Scary, innit?


Guruswami-Sudan algorithm in MATLAB

Read the updates at the end! Comments are disabled because people don’t actually read the post. This is sad to me, since it really shows that the majority of people commenting on this post are really just trolling for a free pass at an implementation, think that I or someone else will send it to them or port it into C for them, and are so lazy that they can’t scroll through the post themselves.

For part of my class project in coding theory this semester I’ve implemented the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Reed-Solomon codes are used widely in practice for error-control coding. For example, CDs use a Reed-Solomon code to provide resilience to errors introduced by scratches or machine error. The math behind RS codes is somewhat complicated, but the idea is as follows. Suppose you have some k symbols of data that you want to encode into n symbols. The redundancy (and hence error correction capability) can be thought of as the difference (n – k). This is the “fat” we add into the data to make it resistant to errors.

RS codes take these k symbols and think of them as the coefficients of a polynomial

f(X) = f_0 + f_1 x + f_2 x^2 + … + f_{k-1} x^{k-1}

The encoder and decoder agree to fix n points {a_1, a_2, … a_n}. The encoding map consists of evaluating f(X) at these n points and sending the evaluations:

codeword = (f(a_1), f(a_2), … f(a_n))

The key is in decoding — if the decoder gets any k symbols correctly, it should be able to interpolate a unique polynomial f through them perfectly (this is from linear algebra). Thus in the CD example, if the CD player can’t read some of the symbols, it can only tell the decoder those symbols that it did read. As long as k of those symbols were received the decoder can recover the polynomial and hence the data sequence.

Now of course the math is a little more complicated than that, but not by too much. RS codes are actually defined as polynomials over the ring F[x] where F is the finite field with 2^m elements, and the encoding is the evaluation of a degree k-1 polynomial on all the nonzero elements of the field.

The Guruswami-Sudan algorithm algorithm works in two steps — it interpolates a certain bivariate polynomial Q[x,y] in a F[x,y], and then factors it into factors of the form (y – f_i(x)). The y-roots {f_i(x)} can be thought of as “candidate polynomials” for the data sequences. The algorithm works in polynomial time and outputs a small list of candidates which is guaranteed to contain the transmitted codeword under certain conditions on how bad the errors are. The real key is that the list will often contain the true codeword even if more errors occurred than the code was designed for.

My implementation is based on a very nice tutorial paper by Robert McEliece, who is a really fantastic writer. It uses the Koetter algorithm for interpolation and the Roth-Ruckenstein algorithm to factor the resulting polynomial. This posting is mostly so that Google will possibly pop up this page if people are looking for MATLAB implementations of this algorithm and don’t want to waste sleepless nights like I did trying to force it to work. Caveat emptor, as they always say.

UPDATE : I’ve moved several times since this post was written and in the meantime taken down the code since implementing this is a common course project. It was tricky but not too hard, and I’ve decided the learning benefits of implementing it yourself outweigh the (now negligible) time savings for projects involving follow-on work.

academia, israel, boycotts (again)

In an earlier post I talked about my discomfort with the idea that a boycott of Israeli academic institutions is an appropriate or effective means of applying political pressure. These recent posts at Left2Right and Crooked Timber discuss a thoroughly backwards way of approaching the issue that may be adopted by a university professor’s union in the UK. According to the NY Times:

The boycott, which has prompted outrage in Israel, the United States and Britain, would bar Israeli faculty members at Haifa University and Bar-Ilan University from taking part in academic conferences or joint research with their British colleagues.
The resolution on the boycott, passed by the Association of University Teachers in late April, would allow an exception only for those academics at the two schools who declare opposition to Israeli policies toward the Palestinians.

This wrongheaded in so many ways that it makes me wonder how these people made it through grad school in the first place. Setting aside the issue of whether or not a boycott is appropriate in the first place, what could this possibly seek to accomplish? As a symbolic gesture it fails miserably because it’s trying to “call out” academics by threatening to make them academic pariahs. It is definitely not an effective way to apply pressure to the Israeli academy because it applies to only two universities. Finally, it’s an attempt to bind union members to a clearly controversial stance and represents an abuse (in my mind) of union power.

The whole thing is like one high school clique ignoring another or some kids giving one person the silent treatment. These guys wish it was like some sort of gang war or Noble Struggle, but it’s just childish and ignorant.

Elmina’s Restaurant

by Kwame Kwei-Armah. This play, set in a West Indian neighborhood in Hackney, deals with gangs and how they affect families. The plot is a complicated mash-up of family tensions and the hard world of the lower class in London. Delroy (Deli) runs a low-end restaurant with his son Ashley, who is angry ashamed that Deli doesn’t stand up for himself against the other neighborhood business owners. The restaurant’s regulars include Digger, a loan shark and thug who fascinated Ashley. In the first act Deli hires a new cook, Anastasia, who tries to turn the restaurant around and falls for Deli. However, when Deli’s brother is killed by the Yardies (a gang) on the way to visit, the whole situation changes. Deli is forced to choose between being oppressed by the gangs or having his life systematically destroyed.

This play was really interesting to read — at times it had that gritty feeling of American Buffalo but had a more ritual feeling to it, emphasized by the prologue and musical interludes involving a traditionally dressed gurkel player. Kwei-Armah creates big, complicated, and interesting characters and then traps them in a small restaurant. The rest is them working things out, with heart-wrenching results. I would go to see this play in a heart-beat — it is big and full of heart.

As far as writing goes, the stand-out aspects of this play were the desperation of all the characters and the unity of place. These gave the play its intense focus and the brilliant fireworks and conflicts.

The People’s Temple

This play is running for a little while longer at the Berkeley Rep and is definitely worth seeing. It tells the story of Jim Jones and the People’s Temple from its inception to the tragedy in Guyana where 912 people died to the present. The director/writer, Leigh Fondakowski, worked on the Laramie Project and this play follows the same format, telling the story through the words of the survivors and surrounding persons.

Jones led an interracial socialist Pentecostal-influenced church called the People’s Temple, starting in the late 50’s in Indiana, then moving to Ukiah, San Francisco, and finally Jonestown, a city they built in the jungles of French Guyana. In 1978, Congressman Leo Ryan visited Jonestown and was shot along with 3 reporters. Then Jones ordered all the residents of Jonestown to take the potion. Over 900 residents complied, forcing their children to take the cyanide before taking it themselves. One of the survivors recalled watching his wife kill their child and arriving too late and holding them as they died. It was harrowing to hear it described.

The play is very good, although perhaps they should avoid so much singing in harmony, since their tuning is a little off (or perhaps someone was sick and it was just off that night). It suffers from a little imbalance of levity — in the first half you have ample time to laugh, and in the last half all the tragedy and dark side comes out. The actors are a strong ensemble, and they skillfully differentiate the roles they play.

I think everyone should see this play, especially if you know nothing (as I did) about the Jonestown tragedy.


Last night I almost got into an altercation with someone who called me “Habib.” I took it as a slur, they meant it as a slur but in a joking way. I really don’t like the kind of person I was last night, and I really don’t like ignorant talk like I heard last night. I need to make changes right quick.

federalism and gay marriage

Don Herzog over at Left2Right has a nice post on the supposed reasons to oppose gay marriage and their mutual incompatibility. He says there are three basic arguments:

1. Family law belongs to state governments. But it’s outrageous for state courts to rule that gay marriage is constitutionally required. That decision belongs to the people or legislatures of each state.
2. “Full Faith and Credit shall be given in each State to the public Acts, Records, and judicial Proceedings of every other State.” That’s Art. 4, sec. 1 of the Constitution. If one state marries gays, it looks like other states would have to recognize those marriages.
3. Same-sex marriage is wrong, period. Marriage must be between one man and one woman.

Now if you are a strong proponent of federalism, then (1) makes sense. However, many people hold (3) but then try to argue (1) while at the same time saying there should be a constitutional amendment to prevent the situations arising from (2).

In fact, I was at a party last year where I was arguing this case with someone and it was clear that they thought (3) but instead were making some specious claims about the state having a vested interest in making babies. When pressed further on that they retreated to (1) with a sprinkling of (2) for justification. I viewed it as a minor success that I could talk them out of the constitutional amendment.

Of course, an arsenal of counter-arguments is only half the battle. But arguing the benefits is much easier, I think. Unless you’re CNN of course. Sometimes the Daily Show makes me hate the world.