Computing distance in the Facebook graph

Is there some nice algorithm for computing the distance between two nodes in a graph, that gracefully fails when they're far apart? I'm asking this prompted by this metafilter question on how to compute the distance between two individuals in the Facebook graph; it seems to me that if someone is at distance 5 versus 6 from me, for example, I don't really care which it is.

Dijkstra's algorithm, for example, runs in time proportional to the number of edges of the graph. (Well, O(E+V log V), but I'm guessing that log V is smaller than E/V.) This is the search algorithm I learned in an algorithms class once. And most algorithms that I've seen -- of course this isn't an area I know a huge amount about -- tend to run in time at least as large as the number of edges of the graph. (Of course this makes sense because one could have to actually look at all the edges of the graph -- such are the pitfalls of worst-case analysis.)

It seems like bidirectional search would work -- if my friends of friends overlap with your friends of friends, then we're at a distance of most 4, for example. (I didn't realize this had a name until just now; it just seems like an obvious idea to me.) But is there some reason I'm overlooking that this wouldn't be practical?

Snowdecahedron redux

A few days ago I posted about the Porter Square snowdecahedron. Here are more pictures of it and pictures of some smaller ones. The project is due to Dan Beyer. He previously made a dodecahedron out of a tree stump (apparently the trick is to make a wedge corresponding to the dihedral angle of the dodecahedron beforehand) and has proposed dodecahedra built of traffic cones as public art for construction sites.

(I found Dan Beyer's site via metafilter; I don't recall how I found the original picture on flickr linked to in the previous post.)

How to win the Ontario lottery's tic-tac-toe game

Jonah Lehrer writes for Wired on breaking a scratch-off game in the Ontario lottery. In 2003, Mohan Srivastava, a geostatistician, figured out a way to crack a tic-tac-toe game that the Ontario lottery was running at the time. In this game, you're given a set of eight three-by-three grids with numbers between one and thirty-nine on them (seventy-two numbers in total) -- these are visible to you when you buy the tickets. After buying the ticket, you then scratch off a set of "your numbers"; if three of these numbers appear in a row in one of the grids, in tic-tac-toe fashion, you win. Since there are 72 numbers on the ticket and they are between 1 and 39, there is much repetition. It turned out that if a ticket contained three non-repeated numbers in a row it was very likely to be a winner.

The article doesn't say how the tickets are turned out this way, though; what sort of algorithm could produce this behavior? But for Srivastava's purpose of demonstrating that it's possible to tell winning tickets from losing tickets with high probability, this was not necessary. Srivastava also points out that this isn't worth it as a way to make money, unless possibly if you could hypothetically get your hands on a pile of tickets, go through them at home, and return the losing ones to the store.

(I learned about this from metafilter. The commenters there, a usually reliable bunch, seem to be split on whether you could return the losing tickets or not.)

A database of applied math problems

A friend of mine teaches at the British Columbia Institute of Technology. They are building a database of applied math problems, at the 11th or 12th-grade level. Their goal is to give students a better idea of "why do we need to learn this?", which is the bane of all math teachers.

They're not asking for calculus problems. But I've taught calculus and I often had the sense, while teaching the "applied" problems, that they were just straight-up asking the students to do derivatives or integrals, with some words added purely as a red herring to confuse the students. I mean, really, if a ladder leaning against a wall falls down, is there any situation in which one cares how quickly the area underneath the ladder is changing? My memory of pre-calculus classes is hazy, because I haven't taught at that level, but I do remember having a pervasive sense that the applications were contrived.

Porter Square snowdecahedron

You may appreciate the Porter Square snowdecahedron. This is what it sounds like, a dodecahedron made of snow. I couldn't find a isnowsahedron but I found these people rolling a giant icosahedral die down a snow-covered hill.

As for me, there's a mysterious dodecahedron-shaped lawn ornament in the backyard of the house I live in in Oakland, and we don't have snow.

How to draw Voronoi diagrams

How to draw Voronoi diagrams by hand. Just to remind you, a Voronoi diagram is associated with a set of points x₁, ..., x_n in the plane; for each point, the cell containing it is the set of points in the plane that are closer to x_i than to any other x_j. I've spent a fair amount of time doodling Voronoi diagrams in boring places, so this is interesting. Apparently they also run into the problem that sometimes it's hard to tell which cells will border which other cells.

Yes, I know, it's been six months since I posted. As you can see, I'm still alive, and I made it through my first semester here at Berkeley. I live in North Oakland, closer to downtown Berkeley than to downtown Oakland, and I find myself describing where I live as "the part of Oakland that's really more Berkeley-ish". More formally, I'm in downtown Berkeley's Voronoi cell, not downtown Oakland's.

(VIa Proof Math is Beautiful.)

Einstein plays dice

Not only does God throw dice, but Einstein does too, or at least a stencil of him on a wall in the Upper Haight in San Francisco does. This post suggests that it may have been by the graffiti artist Banksy. It's been painted over.

More pictures here and here.

It's been painted over, apparently. That's probably for the best, because that means I won't try to find it when I move to the Bay Area.

(Oh, yeah, I'm moving! I got a job at Berkeley.)