I am no longer using LiveJournal. Until my blog gets hacked by a bunch of script kiddies, it will be available here:

http://www.boopidy.com/aj/blog/

Old posts and comments have been imported. So you won’t miss a thing. Thanks!

I'm going to try to introduce you to a band called Opeth. Opeth plays progressive metal*, which sounds scary and inaccessible, and is, a little bit, especially because they use growled or grunted vocals in many of their songs. I'll give you that: when you first hear growls, you might find them disturbing -- or funny. They're not something most people appreciate on first listen.

But Opeth is about a lot more than a few grunts. Their singer is also an accomplished "clean" vocalist, and all the musicians are first-rate. The songwriting is complex and diverse, encompassing an elaborate and intoxifying combination of genres. The result is music of startling depth, beauty, variety, and power.

So I'd like to introduce them to you one step at a time. At their quietest:

"Coil"

Perhaps this is more accessible than you expected. Let's add a two-part song structure (most of their songs go through three to five parts), and some distortion in the second half. This song is nearly eight minutes long, but be patient.

"Face of Melinda"

We're getting pretty kickass here. Same quiet opening, but then -- louder, more powerful, killer riffs. Notice how strong the melodic core of the song is, even at its loudest moments.

Get ready for the biggest shift: this next song is a fully-realized Opeth composition: loud parts, quiet acoustic parts, clean singing, growling, multiple movements, nine minutes long. Right off the bat you'll hear the growling, and hopefully you'll appreciate how it fits into the mood. A guest vocal by Porcupine Tree's Steven Wilson opens up the clean section at 3:25, and by 5:20 we're off in different territory altogether, before hitting the reprise.

"Bleak"

Yes, this is tough to listen to if you've never heard this kind of music before. But if you're willing to put in the time to habituate to the new noises and wrap your head around the song structures, you'll find yourself amply rewarded.

I'll leave you with one last track, which traverses a dizzying breadth of sonic terrain, at 0:00, 2:30, 3:30, 5:05, 7:15, 8:10, and a rhythmically interesting coda at 10:00 that I dare you to try to tap along with the first time you hear it.

"Reverie / Harlequin Forest"

How many people do I expect to convert with this post? Realistically, zero. But it's worth a shot...

* Many people actually label Opeth in the sub-genre "death metal", as opposed to its cousin, "black metal". Though any music labels are generally imprecise, I think of "death metal" as "feeling bad about yourself" and its cousin, "black metal" as "feeling bad about everyone else". I've never really gotten into black metal, this second genre, but I do have a few albums. It's pretty extreme -- there's occasionally animal blood at shows, and the musicians sometimes do crazy things, including burning churches, killing themselves and even committing the occasional murder... all of which I agree is ridiculous. A friend of mine was shocked that I'd even consider listening to black metal, given such behavior, and at the time, I kind of had to admit his point. In retrospect, though, it's very similar to rap (which we both listen to), in that both often glorify a violent, hateful worldview and occasionally live up to that promise in real life. In both cases, I don't think you have to endorse the lifestyle to appreciate the music. Black metal is a little comical in its absurdity, but there are still some jaw-dropping moments (give yourself at least until the "clean" vocals about halfway through this video), and impressive technical prowess (see the guitar work here, a live version of the next song on the same album by the same band).

I actually keep a list of topics to blog about, because it's a lot easier to think of something interesting than it is to painstakingly convert that thought into prose. And I'm lazy.

Anyway, about six months ago, I thought of the following topic. I procrastinated like crazy on it (like I have the other dozen or so topics I have buffered up), until just last week, when I read an article that described exactly the phenomenon I wanted to write about. Good thing... saved me a lot of work. So here's the topic:

Imagine you're good friends with someone. You've known each other a long time, and you've had ample time and evidence to come to believe that your friend is a good person.

Then one day your friend does something mean. Not anything earth-shattering, but definitely something that, if observed in isolation, you'd attribute to a mean person. And there's the crux of it. Do you

1. weigh the action against the body of evidence you've accrued and chalk it up to an anomaly; your underlying impression of your friend is only marginally altered for the worse.
2. assume that your friend, like most people, puts on a public persona, and view the action as an insight past this persona and into his or her inner, true personality. Your underlying impression of your friend is radically altered for the worse.

I've always felt that people disproportionately opt for choice (b). And this article my brother sent me confirms this feeling:

With warmth, the inverse applies. Someone who does something nice, like helping an elderly pedestrian across an intersection, is not necessarily seen as a generally nice person. But a single instance of negative-warmth behavior—kicking a dog, say—is likely to irredeemably categorize the perpetrator as a cold person.

In other words, people feel that a single positive-competent, or negative-warmth, act reveals character. “You can purposely present yourself as warm—you can control that,” Cuddy explains. “But we feel that competence can’t be faked. So positive competence is seen as more diagnostic. On the other hand, being a jerk—well, we’re not very forgiving of people who act that way.”

I guess I understand the rationale, but it makes one huge assumption: that people are drastically different on the inside from how they act on the outside. Furthermore, I'd wager that if you'd have asked someone who chose (b) whether that was the case -- that he didn't really know his friend's "inner" personality -- before the friend committed the act, he'd vehemently deny it.

I prefer to believe the alternative, that any given person has some variation in his behavior (chemical, situational, whatever), and occasionally you'll see different aspects of it. In the end it just makes sense to consider the totality of your friend's behavior. Anything in isolation is simply insufficient. But am I still subject to the phenomenon described in the article, even though I am aware of it?

I really want to do a song-a-day blog kind of thing. These are songs I own on CD that I've ripped. What's a good medium? (Not LJ, I don't think.) Buzz/Facebook? If I embed a flash player (even possible in those media?) is that more legal than just linking to a file? Help me...

Wow. I just found out that Aimee Mann provides the female vocals on Rush’s “Time Stand Still”. Given how many times I’ve heard (a) that song and (b) her albums, you’d think I’d have figured it out on my own. But I didn’t. I’m still surprised, hearing it now.

I've been to a lot of weddings in my day -- 27 by last count.*  The one we went to last weekend might have had the most unique atmosphere, literally. It was on Hang Glider Site #3 at Mount Tam, and the conditions were pretty much whiteout fog. I think we were standing out an outcropping overlooking the sea, but who knows. Anyway, it was super awesome. Congrats to Dave and Natalie!

A while back, I discussed The Meaning of Liff, in which real place names are associated with "things that there aren't any words for yet", and suggested some additional examples. Here are some more:

LUCKNOW (n.)
The experience, marked by a quiet elation, of reading a New Yorker article about a random topic and realizing that it is going to be ridiculously interesting.

NOME (n.)
The combination of irritation and anger that results when one fills a bowl with cereal only to realize that one is out of milk.

HELL'S KITCHEN (n.)
Where such an event takes place.

Okay, that last one's a cheap shot, but I couldn't resist.

-----
* Unfortunately, we're at the point in our lives where we sadly can't attend all of them anymore. Which reminds me: you know you've grown up when (a) the thing you lack is no longer opportunity or money, but time; and (b) you have no desire to be famous.

Casey Affleck has already admitted that his bizarre "documentary" of Joaquin Phoenix I'm Still Here was staged, essentially a self-destructive two-year-long performance piece.

What about Catfish?

The filmmakers insist that it is. Discerning viewers beg to differ.

Is it life imitating art, or is it merely art imitating art?

I haven't seen Catfish, and don't intend to. But hey, it's the internet, so I believe that makes me fully qualified to offer an opinion: the footage is, for the most part, real, but the filmmakers knew what was going on early on and manipulated the events to their liking.

Does it matter whether it's real? Yes, it does. All documentaries expose the viewpoints of their creators to some extent, but my guess is that this one crosses far enough over the line of manipulation to make it worthless.

A few weekends ago my college roommate James came out to visit. We went to Yosemite for four days. It was pretty sweet. Here are some pictures; I picked ones that I liked, so they're not necessary comprehensive, and some might look very similar to each other.

On Saturday, we did a 14 mile hike from the valley floor up to Glacier Point, then down Panoramic Trail to Nevada and Vernal Falls, and back down to the valley. The first 5 miles were pretty strenuous, with a 3200' altitude gain, but after that it was very pleasant and quite beautiful. Probably the most scenic hike in Yosemite. The domes are immense. It's hard to appreciate their size until you happen to notice a tiny-looking tree or three on the top to put things in perspective.

On Sunday, we checked out a number of spots on Tioga Rd: Olmstead Point, Tenaya Laka, and Tuolumne Meadows.

Because we didn't get permits in advance, we waited til Monday for our most challenging hike, up to Half Dome. It was about 17 miles roundtrip, with a 4900' altitude gain. We made great time, about 3.5 hours, up to the base of Half Dome (the top of the sub dome). But the cables up Half Dome were crowded, and it took us an hour to get up to the top. By the way, I last did Half Dome 8 years ago, and in the intervening time I had forgotten how intense the cables are. Even now it doesn't seem that bad... but when you're actually on the cables, leveraging yourself up and down steep, steep granite rendered slick by thousands of human feet, your adrenaline is pumping.

Third photo here courtesy of James. On the last day, we checked out Mariposa Grove, home of some huge sequoias. That last photo is of some moss a staghorn lichen (thanks Chris!) on a sequoia.

Yosemite is a pretty dangerous place, especially in bad weather. Luckily for us, the weather was perfect. If you want to read about some amazing search-and-rescues, though, check out the Friends of YOSAR rescue page. Read some harrowing stories here, here, here, and here. Oh, and there's a good photo showing the steepness of the cable ascent (this shot is taken pointing almost straight down; note, if you can, how small the people and supplies at the bottom are, and imagine climbing it without a carabiner or anything else to tie you on).

I used to use a laptop every day. In my mind, the most important aspects of a laptop are: screen size and resolution; keyboard quality; thickness and weight; and battery life.

If you asked someone today to choose a top-of-the-line laptop, he’d likely pick a MacBook Pro, the 15” model of which has the following key features:

• 15.4” screen with 1440x900 resolution
• Apparently great keyboard
• 0.95” thick
• 5.6 lbs
• 5:20 real-world battery life

Surely an impressive machine. However, in 2003 I got an IBM Thinkpad T40, which has the following corresponding specs:

• 14.1” screen with 1400x1050 resolution
• Amazing keyboard
• 1.0” thick
• 4.9 lbs
• 4:40 real-world battery life

It’s remarkably similar, and actually better on several counts. Sure,

• The processor is slower, but it was state-of-the-art at the time, and was probably more power hungry.
• The screen is smaller, but it’s higher resolution. Also, the 13.3” MacBook Pro weighs 4.5 lbs, so 14.1”/4.9 is still very competitive.
• “Macs have better build quality, blah blah”. Does not appear to be the case, at least for this example. The T40 in question was used every day as my primary computer for years. It’s been dropped, while open and running, at least 5 times, with no ill effects. In fact, it is still running, seven years on, as a streaming Netflix server for our TV. It won’t die.

What gives? I know battery technology hasn’t improved much. But what about everything else? Shouldn’t new laptops be half the weight, or have fold-up “retina display” screens, or something?

Okay, here’s the most advanced laptop I could find with an optical drive… the Lenovo ThinkPad T410s.

• 14” screen with 1440x900 resolution
• Apparently great keyboard
• 0.83” thick
• 3.9 lbs
• 4:10 real-world battery life

I guess that’s decent. But still. 7 years ago, I listened to music on a portable abacus, and now I have it piped directly into the aural processing unit of my brain. Why can’t laptops catch up?

Edit: In responding to a comment, I came across a better laptop with an optical drive, the ThinkPad X301:

• 13.3” screen with 1440x900 resolution
• Apparently great keyboard
• 0.7” thick
• 2.9-3.3 lbs
• 3:40 real-world battery life

You might have heard whispers about a computer scientist posting a game-changing paper on the internet a few weeks ago. Vinay Deolalikar's attempt at a P != NP proof might net him a million dollars. 

More likely, you've never heard about P and NP and have no idea what I'm talking about. If you're curious at all about one of the most fundamental problems in computer science, and why proving a simple statement is worth $1M to anybody, or just want to understand a bit about how CS people think about computers, here's a layperson's guide to P ?= NP.

How hard is a problem?
Let's say you have to look up a name in the phone book. You might start at the beginning of the book and thumb through the letters until you find the first letter of the name you're looking for, and repeat for the second letter amongst the names that start with the first, and so on.

"Let's see... Smith. [thumbs through to S] A, B, C, …. Q, R, S... okay, S. [now thumbs through S to Sm] Sa, Sb, … Sl, Sm... great. Sma... "

Or you might flip the book open to the middle and see if the name you’re looking for comes before or after the names on the open page, and focus on the first or second half of the book, respectively. You'd repeat this halving procedure, getting down to smaller and smaller sections of the phone book, until you’ve found the name you're looking for.

"Let's see... Smith... [opens book to Nelson] that's after Nelson... [open halfway between Nelson and the end, gets Talbot] before Talbot, so between Nelson and Talbot... [halfway between Nelson and Talbot: Quinn] after Quinn..."

Which way is easier? You may have an intuitive idea. Imagine for a minute that your job is to look up names in a phone book all day, as fast as possible. Now you care a lot more about which of these two methods, or algorithms, you should use. You'd probably want something better than a rough guess; you'd want a quantified understanding of difficulty.

There is a field of computer science called complexity theory that deals with classifying problems by difficulty. Classification by difficulty is very useful. For instance,

• If you have two proposed algorithms for solving the same problem (as with the phone book lookup above), you can determine which is more efficient, and thus which one to use.

• If you have a fixed amount of time to prime your thrusters before the space shuttle launches, or else it’ll blow up, you may want to prove that the priming algorithm will take no more than that fixed amount of time to run.

• If you are searching for an efficient solution to a difficult problem, you may be able to expose the problem as something that is simply too hard to solve by traditional means – one that could literally take longer than the age of the universe to solve, depending on the parameters. Knowing this could save you a lot of time fruitlessly looking for a solution.

What does difficulty mean when solving a problem? If you’re a human, you might think it’s a measure of hard work, intuition, and insight. Of these three, computers are really only good at hard work, so computer scientists measure difficulty in two primary ways, time and space.

Say you’re trying to solve a problem, and you're using a whiteboard for your step-by-step scratch work. Time represents the number of instances you write or erase something on the whiteboard as you work through your solution, and space represents the size of the whiteboard you’d need to fit in all of your scratch work (assuming that you could erase work you don’t need anymore along the way). Analogously, for a computer, time is the number of instructions it executes, and space is the amount of memory (RAM) it needs.

For this essay, we’ll only deal with time.¹ How do we measure how much time a given algorithm takes? There are a couple of different ways to measure time: what's the fastest the algorithm could run? The average time it takes over different inputs? For simplicity, we'll focus on the worst-case time: the longest the algorithm could take to run. That way, no matter what parameters we are given, our thrusters will be primed before the space shuttle launches.

And then there's the issue of size. Looking up a name in the Nome, Alaska phone book takes less time than looking one up in the New York City phone book, right? The time it takes to solve a problem with a given algorithm depends on the size of the input to the problem (what you are asked to do – look a name up in Nome, or NYC?). If the input is a list of words, the size is the number of words. If the input is a single number, the size is the number of digits it has. And so on.

Let’s take a simple example. Say you want to sort a list of n numbers from smallest to biggest:

4  13  21  5  6  9  18  12  7  0

(Here, n is 10, but imagine that it could be anything.) How might you sort the numbers? Here’s one way: scan through the list and find the smallest number. In this case, that’s 0. Take that number out of the list and put it aside. Now, scan through the remaining n-1 numbers to find the next smallest number – in this case, 4. Put that next to the 0. Keep repeating this process, removing one number at a time, until you have no numbers left in the list, and a sorted pile of numbers to the side. Perfect.

How much time did that take? Well, you looked through the n numbers and found the smallest one, and pulled it aside; you repeated this process for each of the n numbers in the list. So you took n*n = n² steps to sort the list². We say that sorting numbers with this algorithm, called selection sort, takes n² time. If there are 100 items in the list, it’ll take around 100*100 = 10,000 time steps to sort them. That’s pretty neat! You give me an input – the list of numbers to sort – and I can give you a limit on how long it’ll take me to sort them, without having to do the actual sorting at all.

Here’s another sorting algorithm. Given a list of n numbers, we permute them (jumble them up) in a random order and see if this new order is sorted or not. If it is, great! We’re done. If not, we jumble them up again in a new random order and repeat. This algorithm will eventually find the right sorted order. But how long will it take? Well, to permute the numbers, we select one of the n to be the first number in the new list. Then of the remaining n-1 numbers, we select another, and so on. The total number of permutations is n*(n-1)*(n-2)*…1, otherwise written as n! (factorial). So in the worst case, when we come across the right sorted order last, this permutation sort algorithm takes n! time to sort. If there are 100 items in the list, that’s 100!, or 100*99*98*…, which is big – something like 1 followed by 158 zeros.

So you just saw two algorithms for sorting numbers, with vastly different execution times. How difficult then, is the problem of sorting? We say that a problem is as difficult as the most efficient algorithm we know of to solve it. So in some sense, it doesn’t matter that permutation sort is really slow; insertion sort does a better job, so sorting is at worst an n² problem. This is a crucial point: if the only algorithm you know of is permutation sort, you think sorting is a really hard problem. When you discover insertion sort, suddenly sorting looks easy and life is good. Our classification of problems, then, is often limited by our own creativity and knowledge. There are many problems out there that might be easier – that might be solved with more efficient algorithms – if only we could come up with these better algorithms to solve them.³

In fact, we know of even faster algorithms that can sort in n*log(n) time, which is faster than n², so sorting really takes no more than n*log(n) time in the general case.

What are P and NP?
So far we’ve shown how problems can be classified by the amount of time it takes to solve them with the most efficient algorithms available. From here we can provide a very simple explanation for P:

P is the set of problems that can be solved in polynomial time.

A polynomial looks like n^k: n, n², n¹⁰⁰, etc. So sorting, which takes n² time, is in P. So are searching, greatest common divising, zip data compression, multiplying, primality checking⁴, and a host of other common problems. In fact, with few exceptions, the world of computers is built on algorithms that run in polynomial time. In addition to simple stuff like sorting, generic algorithmic sledgehammers like dynamic and linear programming, which solve problems from spell checking to resource allocation, are in P.

Other problems are exponential: their times look like 2ⁿ, 100ⁿ, and so on.

We consider polynomial problems to be easy: if n is 100, then n² is 10,000, which isn’t too bad. Exponential problems, on the other hand, are very hard: if n is 100, then 2ⁿ is 1 followed by 30 zeros. So if you have a problem, you’d better hope it’s in P and not exponential, or something even worse.⁵ In a broad sense, problems in P are considered practical, and problems harder than P are cause for concern.

NP is a little more nuanced.

NP is the set of problems that can be checked in polynomial time.

By checking I mean: if I pose a problem and you provide a solution, I can check if your solution is correct relatively quickly, even if solving the problem took a lot of time.

For instance, if I give you a really complicated maze, and you give it back to me with a line drawn from start to finish, I don’t have to solve the whole maze myself to verify your answer; I can just check that your line goes from start to finish without crossing over any other lines, which is a lot easier.

Or: if I ask for the prime factors of a large number, and you give me a list of supposed factors back, it’s easy for me to check if you’re right. If the numbers you give me are prime (which I can check in P), and when I multiply them (which I can also do in P) I get my original number, you’re right. Otherwise you’re wrong.

In each of these cases, I don’t have to do the work of solving the problem myself.

There are many other interesting problems in NP, including:

• Given a bunch of integers, can you pick some of them that together add up to 0?
• Given a map of roads and cities, what is the shortest possible trip that visits all the cities exactly once?

Note that NP specifies nothing about how hard it is to actually solve one of its problems; some problems might be easy to solve and others hard. We really don't know. In fact, it is this unknown -- how hard it is to solve problems that are easily checkable -- that is at the heart of P ?= NP.

What does "P ?= NP" mean?
Read "P ?= NP" as "Does P equal NP?" Are the problems in P the same as the problems in NP? In other words, is every problem that is checkable in polynomial time also solvable in polynomial time?⁶

Here's another way to phrase the question. For certain problems in NP, the best known algorithms involve exhaustively enumerating every possible combination of inputs – an exponential task – to find a solution (much like permutation sort, above), even though checking that solution is ultimately easy to do. P ?= NP asks "Are there some problems for which brute-force (exhaustive) searching for a solution is the best possible algorithm, even if the solution is easy to check?" In other words, are some problems so hard that brute-force is the best we can do?

You can begin to see why this is a hard question. You have to show that either:

1. All problems that are quickly checkable are quickly solvable (P = NP). And your proof better hold for problems that we haven't even thought up yet.

2. A single problem that's quickly checkable is not quickly solvable (P != NP). Sure, you can easily show that the best known algorithm for this problem is not in P, but you also have to show that no algorithm for solving the problem in P can possibly exist, whether we know of it yet or not.

We know of many problems in NP that may or may not be in P. (I'll describe one in the next section.) The solutions to these problems can be checked in polynomial time, but arriving at the solutions using the best algorithms we've got takes exponential time. We simply do not know whether polynomial time algorithms exist to solve these problems. No one has invented (or discovered) one yet, and we don't know whether that's because none exist, or because we just haven't been smart enough to find one.

If it were ever shown that P = NP, the world would be a different place. Many problems that we consider totally out of reach could be solved. Sure, a few that we hope are hard (such as ones that would allow a hacker to decode your credit card number when you buy something on Amazon) would become simple, which would be bad. But on the whole, it would be an amazing broadening of powers for computers everywhere.

Life couldn't be that easy, could it? Intuitively, most theorists believe that P != NP: that some problems are hard to solve, even if they are easy to check. But no one has been able to show it yet. For the record, Deolalikar claims to show that in fact P != NP. The current consensus is that his proof is incorrect, even though the underlying claim is most likely true.

And that's P ?= NP.

(Feel free to stop reading here.)

NP-completeness
Of course, there's more to the story than that. Thousands of papers have been published about P and NP. One of the more intriguing discoveries is the notion of NP-completeness. A problem is NP-complete if it is in NP (checkable in P) and "as hard as" any other problem in NP.

What does that mean? It's pretty astounding. If I have an NP-complete problem, and you give me any other problem in NP, I can convert its inputs⁷ into a formulation of my problem and then solve that problem.

So if you give me an NP problem about scheduling traffic, and I have an NP-complete problem that finds cliques of friends amongst all the relationships on Facebook, I can solve your problem by somehow converting your arrangement of cars into a social graph. These conversions can be technical and complicated, but the bottom line is that I can solve your problem with my problem, and so mine is as hard to solve as yours. (If it were easier, then I shouldn't be able to solve your problem, right?) Furthermore, this property holds for any problem you can find in NP; my problem as hard as anything else out there.

There are many NP-complete problems, each of which can be used to solve the other; you could say they're all equally hard⁸. They allow for some interesting implications:

1. If you find a single NP-complete problem that is in P, then all NP problems are in P, since they're all no harder than that single problem.

2. Conversely, if you find a single NP problem that's not in P, then all NP-complete problems are not in P, since they're all at least as hard as that single problem.

Despite their significance, NP-complete problems are not bizarre theoretical constructs. I'll describe one, just to show you how simple they can be.

Imagine you're going on a camping trip and have a knapsack that can hold a given amount of weight, say p pounds. You have a whole bunch of gear that you'd like to take along: a sleeping bag (4 lbs), a stove (1 lb), a tent (6 lbs), and so on. What items do you put in your knapsack so that you get the closest to p pounds of stuff in there without going over?

Amazingly, the best known way to get the correct answer is to enumerate combinations of items until you've found the solution⁹, an exponential task. No one, to date, can do better. If you can – you win a million bucks. More amazingly, this knapsack problem is NP-complete, simple though it is. You can transform any other problem in NP (factoring, summing to 0, route finding, etc.) to a knapsack formulation and solve it.

On the other side of things, people have tried to approximate the knapsack problem with polynomial time algorithms, since solving it outright takes so long. If you can't get the correct answer efficiently, might as well see how close you can get, right? So rather than enumerate all combinations of items, these algorithms heuristically pick and choose certain combinations, sacrificing total correctness for speed. And they've succeeded: the best polynomial approximations can get arbitrarily close to the right answer, though not all the way there. So the problem is NP-complete – super hard – but also very easy to approximate. Crazy.¹⁰

In addition to knapsack, the two problems I described above as in NP, integer summing and shortest trip, are also NP-complete. But other hard problems, such as the prime factorization one, are not known to be NP-complete. It's a mysterious world out there.

If you find any of this interesting, Wikipedia is a good place to start. Oh yeah, bonus points if you can figure out which phone book lookup method is better.

1 Note that since it takes one unit of time to write something down in one unit of space, space requirements can never exceed time requirements. Back to text

2 Well, not quite. The first time you scanned the list for the smallest number, you looked through n numbers. But the second time, you’d already taken a number out, so there were only n-1 numbers. And so on. The real number of steps is n + n-1 + n-2 + …. 1 = (n²+n)/2. In such cases, we look for the "biggest" term – the one that will yield the largest result as n gets larger – and discard the others as relatively insignificant. In this case, n² is the biggest term, so we forget about the rest. Back to text

3 In certain cases it’s possible to prove a lower bound on problem difficulty. That is, you could prove that a problem can’t take less than a certain amount of time, say t. If you know of an algorithm that takes t time, then you can rest easy, because you know that no other faster algorithm can exist. Here’s one example: finding the smallest number in a list of n numbers must take at least n time steps: one each to examine every number in the list. If you ever try to take fewer than n steps, you can’t be examining all the numbers, and I’ll foil you by giving you an input list in which the smallest number is one of the ones you didn’t look at. Boom – you’ve overlooked the smallest number in the list and your algorithm is incorrect. Many problems are complex enough, however, that proving a useful lower bound is very difficult. Back to text

4 Interestingly, primality checking was only shown to be in P in 2002! Back to text

5 Wait a minute, you say. If my problem takes n¹⁰⁰ time, it’s in P, but it’ll still take really long! You’re right: in practice, the actual constants of the polynomial (in this case, the number 100) make a difference. A n¹⁰⁰ problem is a lot harder than a n² problem. And in fact, there are certain problems (such as linear programming) for which an exponential algorithm can find a solution faster than a polynomial algorithm in many common cases. But as n gets really large, even the largest polynomial is smaller than the smallest exponential: n^1000000 is smaller than 2ⁿ (or even 1.0001ⁿ) for very large values of n. And geeky computer scientists like to think very big. Back to text

6 We know that the reverse is true: problems solvable in polynomial time are checkable in polynomial time; just solve them again and see if your result agrees with the proposed one. In other words, we know that all the problems in P are in NP. But we don't know whether all the problems in NP are in P. Back to text

7 For the record, this conversion process must itself take no more than polynomial time. Back to text

8 You can actually differentiate among NP-complete problems by how well you can approximate them with faster algorithms, but that's a topic for another time. (If you are surprised and curious about the fact that problems that are equally hard to solve can be approximated to different degrees, then start reading up, and welcome to the world of theoretical computer science!) Back to text

9 Without bogging you down with details, I'll acknowledge that there are other known ways to solve this problem, but they're all still exponential in the size of the input. Back to text

10 Just for kicks, one more twist: if you add just one more constraint to the knapsack, for instance giving it a volume in addition to a weight limit, you can no longer approximate it to an arbitrary degree of accuracy. Back to text

More critical acclaim, from his own bio page:

He is the winner of the 2009 Damon Runyon Award for Outstanding Contributions to Journalism, an honor previously won by Jimmy Breslin, Tim Russert, Bob Costas, Mike Royko, George Will, Ted Turner and Tom Brokaw, among others. Three times his columns have been read into the record in the U.S. Congress.

He is “the Tiger Woods of sports columnists,” says Bloomberg News.

As for his sports writing, the New York Daily News called him “one of the funniest humans on the planet.” Publishers Weekly called him, “an indescribable amalgam of Dave Barry, Jim Murray, and Lewis Grizzard, with the timing of Jay Leno and the wit of Johnny Carson.”

He is, in a word, impressive.

He's also one of the worst, most unpleasant writers I've ever read. In content alone, he's mean-spirited, self-satisfied, sanctimonious, painfully unfunny (oh yeah, and still mean-spirited), and flat out lame. When you get past his pathetic attempts to adopt the Sports Guy's style (with more faux-authority and far less authenticity), you find out that he's just a giant smarmy douchebag. Oh yeah, and he's also technically terrible. Purple prose, painful metaphors, hyperbole at every turn.

It's kind of astounding to read his columns and then his C.V. and try to reconcile the two. Am I the only one who is flabbergasted by his accolades? Or what am I missing?

(For the record, I like Bill Simmons.)

Edit: Apparently I'm not alone. And there's even this.

Saw Morcheeba last night at the Fillmore on tour in support of their new album. After a seven-year hiatus, Skye is finally back to front the band. My favorite show of theirs was in 2003 -- their last tour before she left -- at the Warfield, and she was in top form.

One of the best songs from last evening was "Crimson", the first track on their new album. It was a surprisingly powerful rendition, with a searing guitar solo by Ross Godfrey.

Here are two live versions from previous shows on Youtube. Of course, neither is able to recreate my mental image of the song or the solo, but hey, what can you do. The first has the best video and sound quality, but the person taking the video mistakenly focuses on the bass player during the guitar solo -- funny, but also a little distracting.

A year ago this past Sunday, Bekah and I got married. It was awesome.

I try not to post personal stuff here, but I will talk about the music, which we had a lot of fun selecting. We played Sigur Ros’s heavenly “Svefn-G-Englar” as we walked down the aisle, had some friends cover Iron & Wine's “Resurrection Fern” during the ceremony, and used songs by Leo Kottke, Luna, and the Magnetic Fields for the slide show.

The dinner and reception were in a barn, and we rolled our own music for that, too. I’ve dug up as much as I could of the playlists (we changed them on the fly, and I only have a portion of the originals), and offer you a challenge: name as many artists and song titles as you can, from only the first 10 seconds of each song. Of course, no Googling or other cheating. That ruins the fun!

Here are the 10-second snippets from the reception, where we stuck with favorites for the most part. There are 48, so the clip is around eight minutes long.

Fairly standard stuff, on the whole. Give yourself half a point for each artist and each song title you can name. Rate yourself as follows:

If you thought that was easy, here’s more of a challenge. We veered off into indie/folk territory for the background music during the dinner – aiming for quiet, pretty songs that weren’t sad (which eliminates about 90% of quiet, pretty songs).

I did leave one song out, because it’s very hard to get – it’s never even been released on an actual album, as far as I know. One bonus point each for the artist, the title, and the original artist of this song. No Googling!

If you’d like you check your answers, post them in the comments below. But to avoid ruining the fun for everyone else, make your text white, as follows: (1) Click on the “Don't auto-format" checkbox. (2) Surround your comment with a <div> tag, as follows:

So, just as in 2002, both England and the USA are out within 24 hours of each other. In fact, it's been a tough few weeks for me, starting with Boston's dramatic loss in Game 7 of the NBA Finals -- which was actually even more gut-wrenching.

It's undoubtably been said many times before: being a sports fan is fundamentally about disappointment, about getting used to losing. In every sport, every competition, every tournament, there is one winner, and the fans of every other team go home losers. Virtually every time you invest yourself emotionally in a team -- and this holds for even the best teams -- you will find your team losing. In fact, due to the nature of tournament play, the loss is often your last memory.

It's brutal.

Of course, it's those rare wins that make everything worthwhile, right? (... right?) And in that sense, I've been amazingly lucky in the last decade or so. Several of my favorite teams have won a handful of championships: UConn ('99, '04), the Sox ('04, '07), and the Celtics ('08). Even teams that I only tangentially root for have had remarkable success: UConn women ('00, '02-'04, '09, '10) and the Patriots ('01, '03, '04). It's been great. And still it burns, every other time.

Here's a question. It's tough to be a sports fan, given how often you're disappointed, and it's amazing that there are so many fans. No doubt some of the appeal is in etched in our DNA, that human optimism in the face of harsh odds that's gotten us so far in everything else we do. (And makes us like slot machines...)

But not everyone likes sports. Are sports fans a self-selected group that has a stronger strain of this irrational optimism? Or is losing something you're conditioned for as a fan, time after wrenching time? And if the latter, is this comfort with losing an ability that translates to other aspects of life? I'm not even sure it would be a good thing, but I'd be curious to know.

Anyway, here's one good reason to watch sports: Donovan's 91st minute GOOOOOL. Check out the commentator first before watching the video.

(^^^ listen to this)

(Oh, by the way, if you're frustrated by the reffing, I can only point you to this post of mine from 2006. I have some new thoughts on the matter -- mostly about how hard it would actually be to implement video replay for live-ball situations -- but I think it's still fundamentally right.)

Pinback is another band I like that you may not have heard of. Umesh has described them as the quintessential "AJ" band, since they embody a lot of characteristics that I like in indie-ish music.

They have three incarnations, all of which in their best forms are immensely listenable: the first and most unique is angular, with interesting rhythmic and harmonic constructions; the second is poppy; and the third is "indie". Here are three respective tracks.

If you don't like any of those three songs, then you won't like Pinback. If do like them, here are some more.

On a side note, it's really irritating to have to share music via YouTube. I used to use Lala, but then Apple bought them and shut them down. If you look at my earlier posts, you'll now find a bunch of broken links. I'm working on a longer-term solution...

Okay, so this has become a bit of a music blog -- but only temporarily, I swear. I have a list of meatier entries to write, but I've been too lazy to get to them. And besides, music stuff is more fun.

So here's something interesting. Check out these three songs. (Give each one at least a minute.)

They are, respectively, Portishead's "Glory Box", Tricky's "Hell Is Round the Corner", and The Beta Band's "Squares".

Notice anything interesting? Yeah, that slinky descending baseline. Coincidence? Of course not. When I first bought these albums about a decade ago, I was flabbergasted. I looked into it, and it seemed that they all sampled the same song, Isaac Hayes's "Ike's Rap II" from 1972:

Ike is the man. I'm still amazed that the Tricky and Portishead albums -- which came out within the span of a year -- would sample the same song. Anyway, it's a solid one.

Well, of course things aren't so simple. At the time, I thought I had made a pretty interesting observation. Naturally, it turns out that there are entire websites devoted to tracking song samples, and I stumbled across one the other day. It turns out that the Beta Band song doesn't actually sample "Ike's Rap II" -- it samples (or, more directly, rips off) a Gunter Kallman Choir cover of "Daydream in Blue" by the Wallace Collection from 1968! (And has its own same-year twin.)

It also appears that Ike himself may have sampled "Daydream in Blue" to create "Ike's Rap II"! Well then. I can't dig any further on that bass line, so props to the Wallace Collection for writing it. Of course, art is theft, and guess what, "Daydream in Blue"'s main chorus (which is not sampled by any of the aforementioned songs) is itself lifted from Tchaikovsky's Swan Lake.

Compare the chorus of "Daydream in Blue" (starting around 0:40) to the melody at 0:29 of this clip.

Of course, Tchaikovsky himself frequently quoted folk songs in his compositions, so who knows how far back that melody goes. As I always like to say, there's nothing new under the sun.

Hrm, or maybe someone else might have said that first...

On Harper Simon's charming eponymous 2009 album there's a song called "Wishes and Stars" in which the last lines are "There are more wishes than stars/More wishes than stars".

Now, Harper's no astrophysicist, and besides there's some poetic license involved there, but the claim piqued my interest.

How many wishes are there? Well, apparently about 100B people have ever lived on Earth. Conservatively overestimating, each person lived about 50 years (the data from 1960, and a pretty high estimate since people living now haven't gotten all their wishes in yet. Historically, over the course of human history, the average life expectancy is likely much lower.)

How many wishes does the average person make? Let's be very generous here. If we assume the average person makes a wish every 10 minutes of every waking hour of every day (yes... we're whiners), we get

6 wishes/hour * 16 hours/day * 365 days/year * 50 years/life * 100B lives = approx 175 quadrillion wishes.

Wow, that's a lot of wishes. Not bad, Harper.

But, as Carl Sagan reminds us, and as Douglas Adams points out to amusing effect, the Universe is a big place. Our own galaxy alone has about 100 billion stars. It looks like there may be between 10 sextillion and 1 septillion stars in the Universe, or about a million stars for every wish. So go ahead and wish upon a star; there's plenty left.

By the way, the album is quite good, catchy folk with a tinge of country. Here's another star-oriented song:

For whatever reason, it has become fashionable to comment on how little Barack Obama has done, or on how poorly his presidency has gone thus far.

No matter happens tomorrow, I would like to state for the record that I think that Obama has done a terrific job in a challenging, adversarial environment and under incredibly difficult conditions. I got your back, dude.

OkCupid is a free dating website that has an outstanding blog. The blog is really interesting because the creators of the site mine massive amounts of user interaction data to expose preferences and inefficiencies, so to speak, in the dating "market". They're fairly rigorous with the analysis, though of course it's hard to draw universal conclusions. Regardless, it's a fun read and provides some insight into human psychology. (Only one entry is displayed per page, so make sure to view "Older Entries".)

I'm happy that OkCupid is getting some recognition for the blog. It has an interesting history. Its creators (or at least their core) all went to college together. After college they founded The Spark, which was an awesome humor/quiz site. It got a lot of traffic, but I'm guessing it didn't make a lot of money, since they then launched SparkNotes, which was a free alternative to Cliff's Notes. It did really well and was acquired by Barnes and Noble. Now they're on to OkCupid.

There are two reasons why I'm interested in their story. The first is that one of the founders, Sam Yagan, was my TA for both of my intro CS classes in college. He was awesome, and a major reason why I got into computer science in the first place. So I'm thrilled he's doing well.

The second is that another founder, Christian Rudder, is one of two members of the band Bishop Allen. They write incredibly catchy indie rock.

Their first album, Charm School, is 100% great. Their second is okay, but the third, Grrr..., is a fantastic return to form, though not quite as consistent as the debut. Find them all here. Anyway, here are some more songs – start your foot-tapping now! Bishop Allen is back, baby.

(As usual, make sure to click on '360p' to switch to '480p'... the sound quality is noticeably better.)

In the spirit of rekindling interest in old favorites, here's another band that I loved, lost, and found again: Morcheeba.

Morcheeba's first albums were fronted by the inimitable Skye Edwards, whose silky voice served as a great anchor for the Godfrey brothers' combination of trip-hop and soul. Check out The Sea and Rome Wasn't Built in a Day for good examples.

Skye left the band in the early 2000s, and they struggled to replace her, releasing 2005's (pretty good) The Antidote with one singer -- and touring in support of the album with a different singer.

I saw them live on that tour, and it just didn't compare the electrifying Skye-enhanced set I experienced in '02. My hopes for a strong future for Morcheeba were dimmed.

I recently picked up 2008's Dive Deep, which witnesses the brothers trying a new tactic: instead of using one vocalist, they rely on several. The result is surprisingly good. Perhaps too smooth in places, but the overall feel is excellent. Here are two of my favorite tracks. (The latter features Cool Calm Pete; Grant would be proud.)

And while I'm throwing stuff out there, here's an old gem from Paul Simon's 1990 album The Rhythm of the Saints. It's not even my favorite song on the album, but it showcases his intricate guitar melodies, evocative lyrics, and beautiful songwriting.

I'd also like to recommend my friend Max's excellent radio show, The Golden Beet on KALX. He's got several shows up on the site, and they're all worth a listen.

As you may know, I like the band House of Freaks. About 10 years ago they led me to the excellent September 67 album Lucky Shoe, on which Bryan Harvey played on a few tracks. September 67's principal member was Shannon Worrell, and I tracked down her (at the time) two solo albums, Three Wishes and The Moviegoer.* They're both quality recordings, and strongly evoke that period of my life whenever I listen to them.

The girl who introduced me to House of Freaks in ninth grade also introduced me to They Might Be Giants at the same time, and I quickly became a huge fan. I lost interest with the release of the mediocre Mink Car album in 2001 (released on September 11th, actually), though I owned every album up till that point and listened to them religiously. For some reason or other, I checked up on them recently, and picked up 2007's The Else a few weeks ago. It's an amazingly terrific album. Here are two of my favorite songs.
 

Anyway, some late night browsing led me to their Wiki site, which revealed that John Linnell's wife, Karen Brown, produced Shannon Worrell's The Moviegoer, and John actually played accordion on it! I had no idea; I had never bothered reading the liner notes to the album since they were handwritten and small. So I just checked it, and there he is. More amazingly, Bryan Harvey and Johnny Hott (of HoF) of also play on the album. So: Harvey, Hott, and Linnell, all on the same obscure, out of print CD that I've owned for 10 years and never knew. Dang.

* Impressively, when I view the album on Amazon, it's out of print and only available for digital download, but Amazon reminds me: "Instant Order Update for AJ Shankar. You purchased this item on May 9, 2000." That's a good memory, Amazon! So "about 10 years ago" is pretty accurate. Amazon also lets me view the entire order, which also included Martin Sexton's Black Sheep (excellent), Magnet's Don't Be a Penguin (nowhere near as good as their other album, Shark Bait), and Luna's Bewitched (also excellent). All in all, a high-quality order.

I watched a LOT of the Olympics last week. Multiple hours a day, in many cases. Padding the several thrilling moments (Shaun White, short-track) and many exciting ones were hours of NBC-sanctioned tedium. I'm burnt out now. Let me know if something cool happens.

Let it be known that I love the Olympics. I love the competition, the variety, and the effort. But it's a complicated relationship.

Way back in 2002, before I had a real blog, I wrote about the Winter Olympics on my old web page :

Also, the events are so specialized and esoteric that I have absolutely no confidence that the athletes at the Games are really the best in the world, in terms of potential. Of course, this is true for any sport, but at least for the Summer Olympics, many more people have tried the events. Every kid growing up in this country (for example) knows approximately how good a runner he is, but no one I know -- not a single person -- even knows anyone who's ever tried bobsledding. Heck, one of my co-workers could have world-champion skeleton potential, for all I know. These Games just seem to have a much greater emphasis on privilege and association than the Summer Games or (especially) the World Cup.

That said (and I really had to get it off my back :), drama and courage were on display to an enormous degree at Salt Lake. It takes guts to put years of your life at stake for a minute-long race. Just being able to compete under such pressure (never mind attaining the skill to do a given event) is an accomplishment. I mean, I got butterflies when I lined up in high school cross country races. I can't imagine what Michelle Kwan felt when she stepped on the ice for the long program.

Unsurprisingly, I still feel this way about the Winter Olympics: they're more about privilege than they are about talent. (I have similar concerns about some events in the Summer Olympics, but less often.) A recent controversy about ski jumping reinforced this belief for me. The IOC decided not to have a Women's Ski Jump event in the 2010 Olympics.

The IOC voted in 2006 not to allow women's ski jumping into the 2010 Games, saying the sport has not developed enough and that it didn't meet basic criteria for inclusion.

Really? So what qualifies as "not developed enough"? From the article:

As many as 1,000 women compete in ski jumping in 17 countries around the world, and about 100 are licensed to compete internationally.

Whoa. That's all? Is that a joke? Another article corroborates:

Rogge said there are 164 registered women jumpers in the world... about 15 "technically very able" jumpers but the rest are not up to world standards.

Okay, so there are hardly any women ski jumpers. A bit scary that it was being considered for an Olympic event. Well, at least there must be swarms of men, since that event qualifies, right? Not exactly: the same article states that there are 2,500 men ski jumpers. That's it! Now, there might be 2,500 registered men, and maybe 10x that amount unregistered. But that's still an insanely small number.

More interestingly, the women are arguing that it's not fair that many other medal sports have even smaller participation.

Supporters of women's ski jumpers argue there are 135 women ski jumpers in 16 countries. This compares to other sports already in the Olympics like snowboard cross, which has 34 women from 10 countries; skier cross, which has 30 women from 11 nations; and bobsled, which has 26 women from 13 nations.

You might want to read that again, to convince yourself that your eyes aren't tricking you. Sure, give these sports 10x for unregistered people, or even 100x -- I'm pretty sure there were more high school cross country runners in my small home state of Connecticut. I don't think any of them are competing for medals.

To be clear, I have nothing against Women's Ski Jump in particular, especially with respect to Men's Ski Jump. (In fact, one article states that the best American female ski jumper, Lindsey Van, recently set a course record, besting all males.) I just think all of these sports are pretty bogus, at least from a competitive perspective. There's no doubt that the athletes involved put in an incredible amount of time and dedication. I'm just not nearly convinced that they're the best talent in the world at what they do.

In the car the other day I mentioned that I was going to start practicing the guitar for real, in such a way that implied that I knew, in some deep sense, how to practice an instrument. A friend inquired about it, and with a little thought I realized that I did in fact have a notion of practicing well.

I developed this notion back when I played the trumpet -- far more seriously and often, and with much greater rigor, than I now play the guitar. Of course, I was still lazy back then, so I didn't always follow the rules, but at least I knew what they were. At any rate, here's how what I think it takes to practice an instrument well:

1. Warm up. A good warmup routine achieves a few things: it helps you improve fundamental techniques through repetition, it prepares your body physically for the current practice session, and most importantly it prepares you mentally. By forcing you to focus on a task that's both challenging and familiar, it helps clear your mind.
2. Use a metronome. You never know how badly out of time you're playing until you use one. Find a comfortable tempo for the exercise you're playing -- and then slow it down by 10-20%. It's always harder to play slow than it is to play fast.
3. Focus, and reject mediocrity. This is the most important and hardest rule to follow. One good hour of practice is worth ten bad ones, and what separates the two is focus: how hard you concentrate while you're playing, and how unwilling you are to let minor infractions pass. Few mistakes are minor enough to truly let go.
4. Keep moving. It's easy to become comfortable with a set of exercises and, eventually, your mastery over them. Keep moving on to newer, challenging material, as soon as you've nailed the current stuff -- but no sooner.
5. Get a teacher. Expensive, but necessary. I'll have to do this eventually for guitar if I ever want to be any good.

Okay, that's all I have.

My friend Grant posed the following interesting question to me:

Say you could go back in time to 1999... and you were to show/tell something that shows how much "progress" humans have made in the past 10 years -- something that would amaze somebody -- what would it be?

A great question, I think. Here are some answers we came up with, with a bit of justification for each:

• Wikipedia: launched in 2001, it now has 3.1 million articles in English and 14 million overall. The #1 information source on the web and a massive testament to user-generated content. (Remember Encarta?)
• Nexus One (or any suitably advanced smartphone): The first gigahertz chip didn't even come out until 2000, and now you can get one in the palm of your hand -- with near-universal connectivity and a beautiful touch-screen that nearly matches the 800x600 resolution of most common full-size monitors in 1999. It also comes with a built-in 5 megapixel camera to boot, and those babies weren't even available to consumers until 2001.
• Avatar: CGI on an obscene, marvelous scale. Art+technology.
• Obama: a black president so soon? Amazing.
• 32GB microSD card: In 1999, the largest hard drive you could get was 37.5GB. Now you can get 32GB in a format the size and weight of your fingernail -- about .0005th of the volume and weight of that big old hard drive.
• YouTube: Only started in 2005, but already has over 100 million videos of all varieties and origins. People watch over 10 billion videos a month -- near 10 hours of video per user. All video will be streamed eventually, but it's staggering how quickly the transition is happening.
• Usain Bolt's 9.58 in the 100m: Maurice Greene makes things complicated here. He ran a 9.79 in 1999, but he's since admitted to buying (but not using... hrm) PEDs. If we take him out of the equation, the 100m world record improved by 0.08s from 1989 to 1999, from 9.92 to 9.84. From 1999 till now, Bolt has taken off a remarkable 0.26s. For a similar improvement from 1989, we'd have to go back to the mid 50s and the era of hand-timing. Even with Greene in the picture it's an amazing feat.
• TiVo: pause, rewind, record TV. Seems like magic. (Actually came out in mid-1999, but I couldn't resist. PVRs are so pervasive now.)

Runners up: Newspapers going out of business (drag timeline to the left), iPod (2001) + iTunes (7B songs sold), eInk/Kindle, Google Street View

Clearly, since we're both computer nerds, this is a limited, biased selection. Which of these is best? What else is out there? Medicine, the arts, the sciences, sports, politics...

Also: predictions for 2020?

The late, brilliant Douglas Adams co-authored a book called The Meaning of Liff. From Wikipedia:

It is a "dictionary of things that there aren't any words for yet"; all the words listed are place names, and describe common feelings and objects for which there is no current English word. Examples are Shoeburyness ("The vague uncomfortable feeling you get when sitting on a seat which is still warm from somebody else's bottom") and Abinger ("One who washes up everything except the frying pan, the cheese grater and the saucepan which the chocolate sauce has been made in").

I acquired this book many years ago because I loved Douglas Adams, but never really got it. After finding a (typo-ridden) copy online, I've a newfound respect for it. Part of the genius, of course, is that the "made-up" words are all place names.

Here are my favorites entries from just the letter W:

WEST WITTERING (participial vb.)
The uncontrollable twitching which breaks out when you're trying to get away from the most boring person at a party.

WINKLEY (n.)
A lost object which turns up immediately you've gone and bought a replacement for it.

WORKSOP (n.)
A person who never actually gets round to doing anything because he spends all his time writing out lists headed 'Things to Do (Urgent)'.

WRABNESS (n.)
The feeling after having tried to dry oneself with a damp towel.

WYOMING (participial vb.)
Moving in hurried desperation from one cubicle to another in a public lavatory trying to find one which has a lock on the door, a seat on the bowl and no brown streaks on the seat.

You get the picture. It's a great concept. Here are a few more I've recently come up with myself:

LANSING (participial vb.)
Saying the wrong lyrics while singing along to the radio, especially in the presence of someone else.

EAST LANSING (participial vb.)
A form of lansing in which one errs by singing the bridge or chorus a verse too soon.

REDDING (participial vb.)
Gingerly raising a hot liquid to your lips in anticipation or fear of it burning your tongue.

(Some might consider this a SPOILER)

In the last two days, I saw District 9 and Avatar, two movies with several similar characteristics: large aliens, oppression by humans, not-so-subtle commentaries about imperialism, DNA mixing, and a crossover human. Both were uber-awesome, though in very different ways. Highly recommended!

For better or for worse, there's a fairly well-established status hierarchy for professionals in the US, with doctors near the top, and janitors near the bottom. Is there a similar status hierarchy for celebrities?

I happened across this old interview with Death Cab for Cutie's Ben Gibbard, in which the following exchange was made (irrelevant parts elided for clarity):

IGN: What do you think of people who start dating actresses when their bands make it super big?

Ben Gibbard: What's my opinion on that? You know what's really strange is Death Cab played in Washington last May. Coldplay headlined the thing. So, all these guys from Death Cab  were in the backstage area getting ready to go on and the bus pulls up and Coldplay gets off and of course Chris Martin is towing Gwyneth Paltrow through the crowd and everybody's trying to do that thing where nobody wants to look, like everything's normal, but this is probably going to be the only time that we're ever going to get to see someone like this up close. She makes her way through the crowd and back and our friend Jed that works at Sub Pop had the best quote of the entire evening, "Great, the one chance I get to meet Gwyneth Paltrow and I'm in a f@#king bunny suit."

I feel that levels of a celebrity are like similar to military rankings, you know? If you're like a movie star, that's like being an officer, but if you're a rock star, it's still like being enlisted. You can only go so high in the enlisted side of the Army. Even if you're the biggest rock-star and you're dating a movie star, even if it's a low rent movie star, you're like way lower than them. It's a weird way to date up, but you're still not ever going to be on their level.

Now, Gibbard's view may be slightly biased -- the people backstage at the show, being in the music industry already, are probably not going to be as impressed with seeing Chris Martin as you or I might be -- but I think it hits home pretty well.

Among celebrities, who has the highest status? Let me rephrase this question to make it more concrete: if you were to run into several celebrities in a mall -- a movie star, a rock star, a reality TV star, a sports star, and a supermodel -- who is the first you'd mention you saw to your friends when you got back home?

Of course, individual preferences may vary, but my guess is that if you took a national average, you would find the following order:

1. Movie star
2. TV star
3. Sports star
4. Rock star
5. Supermodel

Movie stars get the edge over sports and rock stars because they have the unique combination of broad public appeal, longevity, and face time -- everyone knows what they look like up close, so actually seeing them up close is more of a validation.

What do you think?

Trick play is controversial
by David DeBolt
From the Daily Post, Monday, December 7, 2009

With seconds to go in a game that would help take them to this week's national championship tournament in Florida, the Palo Alto Knights pulled a trick out of their bag of plays.

After hiking the ball, a coach on the sidelines started yelling to ohne of the players on the squad of 8- and 9-year-olds that he had the wrong ball. The player walked casually toward the sideline and, during the confusion, suddenly took off, running in the decisive touchdown.

The wrong-ball trick gave the Knights the 8-7 victory and after another playoff win the team reached the national championships in Orlando where they played in a game this weekend.

"That's football"
The trick was questioned by an opposing coach yesterday, who called the move unsportsmanlike. But Mike Piha, the Knight's longtime president, who is with the team in Florida this week, defended the play call yesterday. "That's football," he told the Post yesterday.

The call came against San Jose's Oak Grove Rampage on Nov. 1 in a playoff game. Jess Barreda, who coaches the Rampage, said his players are taught to respect authority and stopped playing once the coach started yelling about the ball.

Players were devastated
"It was just devastating," Barreda said. "All my kids were crying... because they felt cheated." After the game, Barreda heard complaints from parents, including one who asked, "How can that coach sleep at night?" Barreda appealed the game, arguing the play was illegal. The league agreed, but Barreda said the game couldn't be rescheduled.

The loss would have kept the Rampage out of the tournament, but another team dropped out, leaving room for them in Florida and a chance for redemption. The Knights lost their opening game 40-0 and if they lose against a team from Jacksonville, Fla., tomorrow they could wind up playing the Rampage in a rematch. If they meet, they'll ironically play for the Sportsmanship Award.

Hall of fame induction
The Knights, which offer football for kids ages 6 to 14, beat Oakland to reach the national championships. Two of the teams reached the championships, a first for Piha, who coaches the team for 10- and 11-year-olds and will be inducted into the league's Hall of Fame this wek.

When asked about the trick play, Piha said his teams use them often. In fact, Piha's squad used one in their 20-0 loss yesterday to the Tampa Bay Saints.

In this play, the players acted as if they were in a huddle discussing the next play when a center tossed the ball to one of them. The huddle then acted like a massive blocking device for the running, who went all the way to the 10-yard-line before he was tackled, Piha said.

"It was cool," Piha said.

Pretty hard to believe.

In other news, I finally did it. I finally splurged on a purchase I've been waiting a long time for.

That's right: 24 pairs of socks. 24 identical pairs of socks. No more grabbing up to 7 distinct sock singletons (I've done it) with nary a pair in sight. According to my calculations, this purchase alone will reduce my stress level by 23%.

* Don't worry, I'm donating all the old socks.

One of my writing-style pet peeves is the incorrect use of the word "infinitely". As in "OMG, this math test was infinitely harder than the last one!" No, it wasn't.

Of course, there are a few legitimate uses of the word, and props to people who use it correctly. But for the most part, people use it to mean "a lot". Even Malcolm Gladwell, in his latest New Yorker article about football players:

At one point, while he was discussing his research, Guskiewicz showed a videotape from a 1997 college football game between Arizona and Oregon. In one sequence, a player from Oregon viciously tackles an Arizona player, bringing his head up onto the opposing player’s chin and sending his helmet flying with the force of the blow. To look at it, you’d think that the Arizona player would be knocked unconscious. Instead, he bounces back up. “This guy does not sustain a concussion,” Guskiewicz said. “He has a lip laceration. Lower lip, that’s it. Now, same game, twenty minutes later.” He showed a clip of an Arizona defensive back making a dramatic tackle. He jumps up, and, as he does so, a teammate of his chest-bumps him in celebration. The defensive back falls and hits his head on the ground. “That’s a Grade 2 concussion,” Guskiewicz said. “It’s the fall to the ground, combined with the bounce off the turf.”

The force of the first hit was infinitely greater than the second.

So either the second hit didn't happen, or else the first hit was executed with infinite force, which I guess is pretty impressive at the college level. NFL scouts, you watching?

Laptop displays consume 30% of the total energy supplied by the power supply or the battery and represent a substantial efficiency paradox by themselves. On the one hand, they cut power use and physical size by perhaps 50 to 80% relative to the external cathode ray tubes (CRTs) that preceded them. On the other hand, they still exhibit profound, fundamental inefficiencies in their basic design. The power that feeds the display starts at the AC wall plug and is converted in the power supply to DC. But displays require AC power to operate their fluorescent backlights, so the portion of the power that runs the display must undergo a second inefficient conversion from DC back to AC in an inverter, at an efficiency of perhaps 80% to 90%. Of that AC power, about 30% to 40% is successfully converted to visible light in the cold cathode fluorescent backlights, with the rest becoming heat.

Then, because of the inherent opacity of most liquid crystal technologies, 95% of that light is absorbed in the crystals themselves, rather than passing through them to emerge as useful visible light of a particular color.38 In total, then, perhaps only 1% (84% * 30% * 85% * 35% * 5%) of the energy content of the electricity drawn from the wall is actually available in the pattern of visible light emitted from its display that we call “information.” If, to be generous, we consider only the efficiency of the entire chain of components in the display system, rather than the computer as a whole, we would still have to conclude that the system only converts about 2% to 3% of the electrical energy consumed by it into visible information.

I am of course going utterly gaga over Usain Bolt's recent performances at the World Championships in Berlin.

First, there was the mind-blowing 9.58 in the 100m. Keep in mind that before Bolt started running the race for real about 18 months ago, the record was 9.72. He beat his own world record by 0.11s – totally ridiculous.

His astounding performance leads to perverse charts like the 100m world record progression:

He's the last three little x's in the bottom right.

Okay, and then he ran the 200m in 19.19 last night, beating his old world record there by another 0.11s.

Keep in mind that those other guys he's roasting are (with one exception) the other fastest guys in the world. This isn't a high school track meet.

Now, that one sprinter who's missing, Tyson Gay, is actually the second fastest man in the world in the 200m. But his best time is a mere 19.58, so… not in the same league. It's hard to imagine one person being that much better than everyone else in the world. But it's happened.

Bolt is a freak of nature – the first really tall guy (6'5") with enough coordination and footspeed to run fast. The crazy thing is that he's only going to get better. He turns 23 today, and apparently sprinters really hit their prime at around 27.

Furthermore, and this is something I haven't seen anyone else point out yet, his 200m time is slow. For the first time since the advent of electronic timing, the 200m WR is more than twice the time of the 100m WR. The sprinters in the 200m are at top speed for longer: the first 100m starts slow, from the blocks, but the second 100m is at a full sprint. Thus, the 200m is the only track even in which the increased distance also increases the average speed. So you'll find the best 200m times are faster than 2x the best 100m times. You can see for yourself here and here.

Not the case now, as Bolt's 9.58 and 19.19 attest. My hypothesis: he is simply not in good enough shape to sustain his top speed for 200m. In fact, you can see him visibly tiring in the last 20-30m of the race in the video above. As he gets better, we'll see that 200m time drop to fall in line with historical expectations. Before Bolt ran, the records were 9.74 and 19.32, a difference of .16s. So based solely on his 9.58, a 19 flat or so is in the cards.

But he'll get faster in the 100m, too. So sub-19 (fantasy-land, now) is on the horizon. I'm calling it here: Bolt will run a sub-19 200m.

I really like optical illusions, and have posted a few in the past, such as this one:

Those snakes aren't actually rotating; they just look like they are. Anyway, I came across a really cool one recently:

In this case, those green and blue spirals are actually the same color. No, I'm not kidding. Feel free to open up Photoshop to check for yourself, or head here for a detailed look and an explanation. More color illusions of this ilk here, and more illusions in general at the top page of Akiyoshi Kitaoaka's amazing site. Enjoy!

On Friday, weather.com reported that the chance of rain on this coming Saturday -- a day of no small importance to me -- is 0%.

Now that's a bold statement, of course, but a reasonable interpretation of it is: "There is no way it is going to rain on Saturday".

When I checked the weather again today, weather.com now reports a 20% chance of precipitation.

How is this possible? My not unreasonable interpretation of the precipitation chance number N on day D is: "There is an N percent chance that it will rain on day D: given the initial conditions present today, if day D were to occur 100 times, it would rain on N of the times."

By this logic, 0% and 100% are very dangerous numbers. If a percent ever falls to 0% on a given day in advance of D, it can never leave 0% on subsequent days before D. Same with 100%. There is no occurrence that could induce a change. (Assuming arbitrary precision, which we'll discuss later.)

I think what weather.com really means is: "Given what we know now, there's an N% chance of rain on day D. But we may know more later."

Also reasonable, but a really irritating interpretation for those of us who just want to know what the weather will be like. We don't want to have to worry about what weather.com does or doesn't know. And I think weather.com could account for this uncertainty by an empirical analysis of past 0% and 100% claims. How often did they have to change that number before day D? Add in a little factor that accounts for this uncertainty.

I don't know enough about weather prediction to make any better suggestion at the moment. Also, I suspect that their desire to not appear overly precise, manifested in their use of only a single digit of precision in their percentages, is a real problem here. Anything under 5% might appear as 0%.

So that’s another good excuse. But the fact of the matter is that when I see 0%, I want to be able to plan my beach party with confidence. Don’t destroy my confidence, weather.com.

Damn. There's so much beauty in music it's absurd. What trick of evolution allows it this level of emotional resonance?

When I was in high school, someone gave me a collection of Edgar Allan Poe's short stories. Of course, all of his classics ("The Fall of the House of Usher", "The Pit and the Pendulum", etc.) were present, but at the very back was a story I had never read before, called "The Imp of the Perverse".

The Imp is a sneaky guy who lives in your head. He's the one who implores you to pull the red stop cord on the train, or take a step over the edge of the Grand Canyon – or to drop a snide comment at your family reunion. He eggs you on with a simple motivation: to see what happens when you do exactly the thing you're not supposed to do.

I was fascinated by this concept, mainly because I often feel this temptation. (I feel like it should be as well known as schadenfreude – it's got to be as universal, and there's no other good term for it.)

Anyway, I was delighted to read an article in the New York Times about the Imp featuring Daniel Wegner, who wrote the awesome The Illusion of Conscious Will. The article mentions that actively fighting "perverse" thoughts can paradoxically increase your chance of acting on them.

I had a related meta-problem: since I've read about the Imp of the Perverse, I'm always waiting for him to arrive. So as soon as I spot that tempting "Emergency Stop" button in the elevator, I think "Good ol' Imp", and before I know it I'm dreaming of pushing the button. One step closer.

I have a very simple technique for highway driving: I drive 13 miles an hour over the speed limit. This is usually fast enough to place me into the fast lane, but slow enough that it's not worth it for cops to ticket me. I've driven roughly 30k miles and have never been pulled over. So I think it's a good strategy.

However, the Bay Area is tricky about speed limits. Changes are frequent, and can vary by up to 20 mph (50-65 on 101S in SF; 45-65 on 880N in Oakland). So if I'm cruising at 78, I can get into big trouble if I don't notice that the limit just dropped to 45. I want some kind of phone or GPS app that will just tell me what the current speed limit is. (Even better: one that will beep when I exceed 13 mph over it.) Anyone? I don't really care about speed traps; I just want to know the speed limit.

I've been listening to a lot of American Analog Set lately. My friend Lonnie introduced me to them in 2000 and since then they've been a constant, steadying presence in my life. In fact, one of their songs was the genesis of the title of this blog. For various reasons I've listened to them less frequently of late, but they're back.

I guess you could classify Amanset as "drone-rock": whispered vocals, fuzzy or chiming guitars, languorous tempos, repetition, melancholy lyrics. A warm blanket. It's easy to find them boring if you don't listen carefully enough. But if you do, and let the music feel for you, it's a powerful experience.

Here's a YouTube playlist of some Amanset songs.

What's my favorite Amanset song? None of these, actually. Why spoil the fun?

I may continue this trend of exploring bands that I like. Next up might be Porcupine Tree, just because Steven Wilson keeps pumping out amazing stuff.

How do dogs recognize each other?
You know what I'm talking about: dogs will ignore other species, but bark at and interact with each other. Now that doesn't sound like an impressive recognition task, but consider that dogs have been bred over the last few thousand years into a staggering variety of subspecies, with radically different features, sizes, and proportions. How does a Great Dane know that a Chihuahua is a dog? (And vice versa; the chihuahua essentially has the brain of a wolf in the body the size of a rodent. That must be confusing.)

The first explanation that comes to mind is smell: dogs smell the same, and they have great noses, so it's easy to tell if another animal is a dog. But I've seen many dogs bark at others – from behind a closed car window. So it's something more sophisticated.

More possibilities: smell is first, sight is second, dogs only bark at similar-looking dogs if they can't smell, etc.

Google didn't come up with much. The best I could find is "Dogs too have their own scent and smell to establish who is who, sniffing around each other's bodies. Dogs also use sight to first look and decide if it is a dog they are looking at and then sniff to find out if they know each other."

I don't have a dog (though I think they are awesome), so if you do I'd love to hear your thoughts.

Shopping by calories
I don't know what the deal is with my metabolism, but I have to eat a ton of food each day. If I don't eat breakfast, I won't survive till lunch, and even after a big lunch I'm hungry by 4pm. When I go to a convenience store to grab some snacks, I often find myself shopping by calories: which item will give me the most calories per dollar? This sounds perverse, but I can't help it. And I've found lately that I do this subconsciously even when I'm shopping in a grocery store! Weird. Does anyone else do this? Kent?

Obama's Egypt speech
A thing of beauty. Read the transcript (it's easy and pretty short). It's nuanced, bold, and inspiring. Some people have been complaining that it's all words, no action. But the speech itself – just words – is a huge step forward. I can't imagine Bush even attempting this. Progress has to start somewhere.

An A-Z Music Project update
Earlier this year I started listening to all my music in alphabetical order. I had the ambitious goal of finishing by the end of the year. Well, there's no way that's going to happen. True, I had a very busy semester, one that didn't leave much time for listening to music, but I'm now only halfway through the Bs (Bonnie "Prince" Billy, to be exact, and 70 hours done of 90 total in the Bs). My new projected end date: Jan 2012. Really?

When you get your Ph.D., you don't feel euphoric; you feel relieved. It's as if someone pulled a knife out of your back.

• I love teaching. I TAed two classes and taught another. Loved them all. Teaching is now definitely a long-term career goal of mine.


• I love coding. NewsDog, Sudoku Slam, Total Fragmentation, and now Modista. There's a joy in good engineering, a beauty in elegant design, and real satisfaction in making something that people can use.


• I like, but don't love, research. Sadly, I'm now cynical about "selling" research, choose-your-own benchmarks, and the chance that anything cool will ever get used in the real world. Some people love the thrill of it, but I guess I don't. When I started, academia seemed purer than business. But it quickly became clear that not much is different: the currency is simply fame instead of money. At the same time, I'm proud of what I've done, even if it won't lead to anything practical. There's some nice stuff in there, I suppose. (I still think that the proofs Bill and I did for the unpublished bin-packing paper are the most elegant I've contributed to.)


• I love California, as a perusal of the photo-entries of this blog will attest.


• I love playing the guitar, and wish I could play more often. Soon, perhaps.


• I love playing ultimate (frisbee).


• I love Bekah.