Interesting Stuff

Bonus nerd points to anyone who gets the reference in the title.

The story so far: three honors students on the Duke lacrosse team were accused of rape after attending a party at which a stripper claimed to be gangbanged. The media dragged them through the mud, talking about how horrible they were to rape this girl. Two years later, they were proven wholly innocent of any wrongdoing (mostly because they left the party before the rape purportedly occurred, and the DNA evidence did not point to them in any way whatsoever). Now, the head prosecutor for the case has been disbarred due to unethical conduct during the trial. He was apparently running for public office, and wanted to use the case to show how he’d crack down on crime. He frequently told the media how he was going to make life horrible for these guys, and then proceeded to hide the results of the DNA test from the defense attorneys for months because it would have shown that they were not in any way guilty. I’m glad to see this has happened and former district attorney Mike Nifong plans to accept the disbarment as a fair consequence of his actions.

There seems to be some push-back about my previous allegations that it was an invasion of privacy to require all government labs employees (even those without security clearance) to submit to investigations of their medical, military and financial records. When pressed on the issue, I argued that it seemed wrong because it unnecessarily pries into one’s personal life. Well, an employee at JPL has written a much more eloquent discussion of it to his congressman. In it, he claims that the Privacy Act of 1974 makes it illegal for a government agency to obtain these records without voluntary written consent, and these people have been given the choice “of either waiving our rights as guaranteed by law and the Constitution, or losing our jobs.” He furthermore states that this will have a chilling effect on the workplace environment because it sets the precedent that the government can come in and request any records it wants for no particular reason. Goddard Space Center employees are similarly disconcerted, and further echo that this “consent” to private records is hardly voluntary and borders on coercion.

I can understand that it’s important to have in-depth investigations into anyone who is granted clearance to work on sensitive material, and that it’s important to only allow people with clearance to have access to this information, but it sounds like this investigation is not going to grant anyone such clearance (though those who already had it are likely to keep it). I still don’t see how the government can request this of citizens that it will not treat as having special clearance: if you want to screen these people, give them clearance (which comes with a $10,000/year raise, which the government is loathe to grant), or treat them like the ordinary citizens as which they have been classified and accord them all rights to which they are entitled by law (take that, preposition danglers!).

Even though my blog is (edit: formerly) titled “Civil Liberties and World News,” I haven’t posted on either of these subjects in a month and a half. It’s time to return to that theme.

Former Secretary of State Colin Powell has started calling for the closure of Guantanamo. I fear it won’t be closed until we have a new president (and possibly not even then), but it’s nice to see that more people are standing up and saying that everyone should have a right to a trial. Moreover, a recent court decision stated that the US cannot indefinitely hold prisoners without trial. It would be fantastic if this kept up momentum. We’ll see what happens.

Also, the Massachusetts legislature defeated a proposed amendment to ban gay marriage (if the measure had passed, it would have gone to a public vote in 2008). There’s one tricky part left, though: a law almost a century old that states that non-Massachusetts residents can’t get married there unless the marriage would be legal in their home state. This was originally intended to fight interracial marriages. Let’s hope this law gets repealed soon!

In more worrying news, minorninth writes that national labs (including JPL) are putting tighter security clearances on all employees, including janitors and secretaries. They are now required to disclose drug use (edit: apparently this is currently legal, although many people think it shouldn’t be), financial records, their armed services numbers, and other totally inappropriate things. If you actually work on a sensitive project, there’s even more: they want to know about your international vacations and medical history (edit: upon further inspection, this looks like this part might actually be an acceptable thing, too, since these people have been granted special clearance by the government). The worst part about this is that the mainstream media doesn’t seem to be picking up the story at all, which is really too bad. I hope more people find out about this before this becomes the de rigeur.

I think that I’m going to give up trying to solve the Hat Problem, though I’ve come pretty far (for background, see my original description and its follow-up post). I’ve now solved the N=5 version (with surprising results!), and gotten a pretty good framework around the problem: My final analysis of the Hat Problem, including a reduction to the Minimum Dominating Set problem, source code for a better program to search for solutions, and an optimal strategy for N=5 →

Yesterday, I wrote about the Hat Problem. I figured out some more late last night, but haven’t had a chance to post until now. I cancelled my brute-force program because I figured out the solution to the 4-person version: have 1 person pass all the time, and have the other 3 people pretend it’s the 3-person problem. I know this because I got an upper bound on the best strategy: with N people, you can never do better than winning N out of N+1 times (so the solutions based on Hamming codes are always optimal). If you add up all the non-pass responses over all possible hat configurations, you need an equal number of correct and incorrect answers (otherwise, the chances that your own hat is red are not independent of the colors of everyone else’s hat, and probability is broken). The best you can bunch up the wrong answers is to have everyone guess wrong at the same time, and the best you can spread out the right answers is to have each right answer in its own hat configuration. So, for every time the group loses, you can have at most N wins, and the best chances you can ever get are N in N+1.

How does this help in the N=4 situation? We now know that best you can do is win 80% of the time. Moreover, there are 16 distinct hat configurations. Winning 13 of them would be more than 80%, so we must win fewer than that many. However, we can win 12 of them by reducing ourselves to the N=3 version, so we know that’s the optimal solution. For N=5, there are 32 distinct hat combinations, and the optimal strategy will win at least 24 and at most 26 of them (but I don’t know the exact answer). For N=6, the optimal strategy will win at least 48 and at most 54 of the 64 possible configurations. The brute-force method won’t finish within our lifetimes for N>4, so I can’t try that again. Any other ideas on how to progress? FWIW, I’ve found a second way to get 75% success when N=6.

(Edit: see part 3 for more on the problem)

I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this:

N people walk into a room and a hat is placed on each person’s head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else’s hat, but not the colour of their own. While in the room with the hats, no one is allowed to communicate with each other in any way at all. Everyone is then lead into separate rooms, and asked the colour of his or her own hat. Each person can choose to answer or to pass. If at least one person answers correctly and no one answers incorrectly, the whole group wins. How do you maximize your chances of winning?

The naive solution (before entering the room, pick one person who will guess Red and have everyone else pass; chances of winning are 50%) seems easy enough, but there are more complicated solutions that do better. For instance, with 3 people, you can win 75% of the time: if your comrades have the same colour hat on, guess the other colour. If they have different colour hats, pass. The only time you lose is when everyone has the same colour hat. Note that a person who chooses to guess the colour of their hat is still wrong half the time (i.e. probability isn’t broken), but we’ve spread out the occurrences of correct answers and bunched all the wrong answers on top of each other. Apparently you can use Hamming Codes to win with odds N out of N+1 when N is 1 less than a power of 2, but I haven’t seen an explanation of how that works yet.

Apparently, this is an unsolved problem for all other N, though. I have written a Java program to use a brute force method to find the solutions, and it easily verified that the best you can do when N=3 is 75% (using the strategy described above). The problem with this brute force solution is that its running time is O(2^n * 3^(n*2^n)), which makes it rather unwieldy. I’ve started running the program to solve the N=4 case, and I hope it will finish by tomorrow afternoon. edit: I dramastically misunderestimated the time needed to run this program. It will hopefully be done by Thursday. I will not use it to find the solution for N=5.

As usual for subtle and tricky topics, the Wikipedia page is wrong in subtle and tricky ways (at least, it was when I wrote this), so don’t bother looking for more information there.

(Edit: I continue working on this in part 2)

Today I got to hear New Mexico governor Bill Richardson speak about his aspirations to be president. He has lead quite a distinguished life of public service: he has also been the ambassador to the United Nations, and the US Secretary of Energy, as well as serving in the House of Representatives. With the possible exception of John Dean, Richardson has impressed me more than any other political candidate I’ve heard of. More about Bill Richardson than I ever imagined I’d write →

I installed ScummVM this evening and have been playing classic LucasArts games. I’ve verified that Monkey Island and Sam and Max seem to work, and they’re as fun as they ever were. These were created back in the day when games couldn’t depend on their graphics to be entertaining, so they actually had to be witty and humourous. Ah, good times!

Most of my friends know that I really like the roguelike game Linley’s Dungeon Crawl and play it often (it’s similar to NetHack and Angband, if you’re familiar with those). In it, you wander around an (ASCII art) dungeon fighting monsters and getting equipment and treasures. The object of the game is to get the fabled Orb of Zot, which is in the Realm of Zot. You can get there from the dungeon by opening the Portal of Zot using three Runes of Zot (see, there’s a theme here…). It has a wonderfully detailed play structure, and provides hours of entertainment.

The only problem, in my opinion, is that it’s impossibly hard: not only have I never won in my 6 years of playing, but I’ve never gotten a single Rune. There are also a few bugs (most notably, it seems to lock up if you’re controlling your teleport destination). I had thought that development stopped in 2003, but it turns out I was wrong: Linley and his friends stopped developing, but there is a branch called Dungeon Crawl Stone Soup that continues on. It has some really nice extra stuff added in. For instance, if there are no monsters around, you automatically pick up gold, food, potions, and certain other objects that you almost certainly want to get. This turns off if you can see a monster. The targeting for ranged weapons/spells is much more automatic. It now has a path planning algorithm in it so that you can walk to any location in the level (and it automatically stops if you encounter a monster along the way). The morgue files (summaries of your character after you die) are much more detailed. Event messages, stats screens, and your inventory are more detailed. It’s still impossibly hard, but DCSS makes some of the basic mechanics much simpler. This is great!

If you’re interested in a fun, easy-to-learn game that offers literally unlimited play, give DCSS a try.

As tech/legal blog Ars Technica reports, it seems that the Bush administration is trying to retroactively pardon the telecoms for violating the privacy and Fourth Amendment rights of their customers. Remember back in 2005 when it was revealed that the NSA uses warrantless wiretaps of most phone lines? Well, the Electronic Frontier Foundation, bastion of freedom that they are, continue to battle AT&T and the government over it. They have fought past the State Secrets issues, and have continued to advocate for the privacy of US citizens.

Well, now it seems that there is an appropriations request sent to the Senate Select Committee on Intelligence that would retroactively pardon the telecoms of all wrongdoing concerning the warrantless wiretaps. If passed, it will kill the EFF’s case dead in its tracks. I strongly suspect that if Congress read this legislation it would not pass, but it’s been pretty well established at this point that very few lawmakers actually read the legislation they vote on. As always, you can write to your Congresspeople about the issue (though the default text in that link is only about the warrantless wiretaps in general, not this latest development). We’ll see what happens…

It seems that users of Digg posted the AACS key (the DRM used in HD-DVD and Blu-Ray) recently. In response to fears of DMCA-based lawsuits, the Digg executives attempted to remove the key from their site. However, so many Diggers fought back by reposting the key that Digg now stands with them and will no longer attempt to remove it. As Digg founder Kevin Rose wrote,

[Y]ou’ve made it clear. You’d rather see Digg go down fighting than bow down to a bigger company. We hear you, and effective immediately we won’t delete stories or comments containing the code and will deal with whatever the consequences might be.

If we lose, then what the hell, at least we died trying.

Hurrah! This, coupled with Steve Jobs’ take on DRM (which caused Apple to sell DRM-free music on iTunes), makes it look like industries are thankfully turning against DRM. The whole idea of DRM is laughably otiose; I’m still surprised anyone thought it would work in the first place. “Gee, let’s take data we want users to have, encrypt it, give the users a way to decrypt it, and hope that they don’t watch our decryption process when they run it.” Even without considering the analog hole, this isn’t going to work. If you give someone data in a format that they can use, by definition they will be able to use this data for their own purposes; there’s no way around it.