Thursday, December 25, 2008

The end of the world

This is just beautiful. It's Pink Floyd's "The Great Gig in the Sky" set to a Discovery Channel simulation of a 500km asteroid impact.

(Watch it in HD. "But how? It's Youtube!" Trust me. This is cool.)

Could it really happen? Probably not anytime soon. 99942 Apophis has the record for highest Torino scale risk estimate so far... at two out of ten. This was back in 2004 when NASA estimated a 1-in-300 chance of collision in 2029. It's known now that that won't happen, but if it goes through the exact right ~600-meter "gravitational keyhole" in 2029 will be on a collision course for 2036. NASA gives that 1 in 45000 odds. If it does happen, though, it will release as much energy as 880 megatons of exploding TNT. The Mt. Krakatoa explosion -- the biggest known volcanic explosion -- was equivalent to about 200 MT TNT and caused unusually cold, long winters for three years in 1883. The biggest man-man explosion so far was "Tsar Bomba", which was a 50 MT hydrogen bomb. For a few nanoseconds in 1961, it lit up an island north of Siberia with about 1% the power output of the sun.

Nevada atomic bomb test in 1951

In other news, it's Christmas Day. I've just one-upped the Grinch.

Sunday, December 21, 2008

Dr. Markov in da house

Last week, in CS106X, I programmed Boggle.

Boggle is played with a set of cubes that have letters on each face. You shake them up, put them in a grid, and try to find words made of adjacent dice faster than the other players can.

Computer Boggle is different. It gives you time, letting you find as many words as you can, and then beats your score by an order of magnitude or so by finding all the remaining words on the board that are in the (huge) Scrabble player's dictionary. You can also play 5x5 "BigBoggle" instead of the standard 4x4, in which case the computer generally beats you even more thoroughly.

One of the cool things about CS106 is that they don't just want solutions, though. It's good style to extend them in some way, and solve some additional problems that weren't in the assignment. For Boggle, I wanted to write code that would find boards with unusually few (or many) words, using only the standard cubes.

So I tried Markov chain Monte Carlo, which I'd Wikied a long, long time ago when I was really into raytracing.

In a nutshell: the algorithm tries to find a global minimum of a function that can be sampled and which is roughly continuous, but which may be in many dimensions and may not have any other nice properties.

You start with a guess.
At each step, you find a distribution centered at the current guess and randomly sample it. If you know what the global minimum should be (e.g. zero) the variance of the distribution will vary with the cost (the value of the function at the current guess), so that if you're far away from the minimum, you're sampling over a wide area, while if you're getting close, you make more incremental guesses. Each 'probe' sampled this way is evaluated, and then you randomly decide whether to accept or reject it, depending on its cost. If the probe cost is significantly lower than the current cost, then you almost certainly accept it, and if the cost is significantly higher, then you almost always reject; in between, it's a toss-up: if you accept, then that probe becomes your current guess, and if you reject, then you keep probing.

Doing all this with Boggle boards took a bit of approximation and rule-of-thumb coding because I don't know a way to actually define a probability distribution over the set of possible Boggle boards. Instead, I defined 'swapping' as taking two cubes at random, switching their places, and randomly rotating each one. I started with a standard, randomly-generated board and, after each evaluation, did a number of swaps proportional to my cost function, with a maximum of about ten. When the guesses started getting so good that I wasn't switching any cubes, I picked single cubes and rotated them randomly to create new probes. The idea is similar: the closer you get to a global minimum, the closer your probes are to your current guess.

I made two cost functions, one preferring boards with lots of words and and the other preferring boards with few words. I already had a function that could quickly search a Boggle board and find all the words on it.

The result: it worked. I was surprised.

BigBoggle boards tend to have around 150 words on them. Here's one with no words at all:

On regular boggle boards, the computer will score ~90. Here, it scored 917:

The code is private because of academic policy, but if you want to play with the program, it's here.

Markov chain Monte Carlo rules.

Friday, December 19, 2008

Penetration-testing national security

The TSA is ridiculous. Bruce Schneier just posted an article about bypassing airport security. Apparently, contractors, repairmen and others enter airports -- sometimes with utility vans -- and get tarmac access, often without going through security.

Meanwhile, I wait in line to have my coke taken away because it's more than 3.5 ounces of liquid, and send my my Croc sandals through an astoundingly expensive scanner. The last time I went through security at Salt Lake International, I counted twenty-two TSA workers. It was early in the morning and there was no line. Four of them were working and the other eighteen were chatting in two big groups. All part of what Schneier calls security theatre.

All this security (which is dubious to begin with) is more than canceled out by negligent (or simply stupid) attitudes towards the simpler and more mundane risks that airports face. I'm sure that these security-nullifying attitudes vary widely from airport to airport, and even from employee to employee. I'm referring to bad habits that become part of the work culture -- like not asking for unknown people's ID (@Swede) and letting vans onto the tarmac with nothing more than a contractor logo (@WarLord).

Here's what I wish the government would do -- not just the TSA, but the NSA and others as well: pen-test national security. Send security contractors posing as contractors to airports and see if they can get in. Can they get a piece of unchecked luggage onto a plane? Can they leave without getting caught?

Clearly, there would need to be a robust vetting process to avoid costly lockdowns when the intrusions do get caught. Maybe, the first thing airports would do with a suspected breach would be to call directly to a national authority (TSA, for example) and check if it's a test. This extra complexity would add some cost and some potential security flaws.

Still, I think it would be a vastly better use of money than most of what the TSA is doing now. It would decrease overall risk significantly because airports would have a real, month-by-month financial and legal incentive to ensure real security. Most importantly, it would bring some accountability to airports and to the security programs that operate in them. There would be actual data on how frequently and severely trained, funded attackers can compromise various systems at airports. Security performance could be compared between airports, between security programs, and over time.

Nothing screams "wasteful theatre" louder than a $4.18 billion (FY2008) TSA budget and no real, quantitative evaluation of its effectiveness. Let's pen test airports and find out how well the security systems really work ... or if they work at all.

Thursday, December 4, 2008


The internet makes lots of tasks infinitely easier than they used to be. Want an executive summary of the War of 1812? Check Wikipedia. Want to know more? Keep reading. If you're really hardcore, the article lists eighty-two scholarly references. Need an obscure book printed by some shop in Khazakstan? Amazon can probably ship it to you for free in ten days or so. Want to convert a kilowatt hour into BTUs? Google "a kilowatt hour in btus". I have no experience here, but I bet that before the web, lots of these tasks would have taken minutes or hours rather than seconds.

Isn't it strange, though, that such a powerful tool for getting stuff done gets used so extensively for the purpose of not getting stuff done? I can't think of another way to explain the fifty-or-so bits of chatlist spam that land in my inbox every day, the SuperPokes, the pirates, the ninjas, the lolcats, and everything else along those lines. Even respectable, otherwise interesting sites like Digg and Youtube are filled with mildly funny, mildly shocking, and mildly sexual banalities.
A while ago, I posted about Twitter, the flagship time-waster-in-chief of all web 2.0 apps. Never before has humanity been this effective at wasting time.

I don't think that lost time is the real problem, though. When the novelty wears off and everything else they could have done with all that time sinks in, people will stop. I'm worried about money.

Parallel to this Cambrian explosion of "web 2.0" apps, replete with tweets, pokes, nudges, posts, threads, and lists, there have been all sorts of new revenue models, further and further removed from the sale of actual goods and services to consumers. Take Slide, Inc, which recently got a $500m valuation from some venture capitalists. It makes slideshow widgets (and little gems like "SuperPoke Pets!") which it plans to monetize by integrating targeted ads into users' slideshows. Many of the ads I see (and ignore) all the time are already advertise other ad-supported sites that don't actually sell anything. It's only a matter of time before I see some ads for Slide.

I think that the system by which dotcoms are funded today looks suspiciously like the way they were funded in the nineties. People are spending way too much money building castles in the air.

Someday, people will tire of spending so much time connected to each other, wasting each others time. The torrent of tweets, pokes, FWD:fwd:Fwd:Fwd:funny pics, and all their unholy brethren will start slowing down as people take back the time that used to be theirs. Maybe someday, sending pointless emails to a chatlist will have the same social stigma that shouting across a crowded room might have now. Maybe the parents of 2015 will tell their kids to finish their homework before they comment on each other's blogs. Maybe they'll warn their kids that too much Twitter rots your brain, or that Facebook bullies are probably just looking for attention and are best left ignored. Maybe someday, I'll log into Facebook and nobody will care what my hooker name would be. I can't wait for that day to come!

Let me skip back for a moment, to the first stock I ever owned ~ two shares of Microsoft, back in 1998 when I was in second grade. My best friend's dad thought that a market in which grade-schoolers own stock couldn't possibly be sustainable. He was right. Today, we've got a market in which investors bet billions on web startups with Rube Goldberg business plans, with almost no connection to reality. They're betting on people barely older than myself trying to capitalize on the time-wasting habits of people, often a lot younger than me, by showing them ads. As people become savvier and the web becomes fully integrated into our culture, my guess is that many dotcoms will be winnowed out in a second crash.

Saturday, November 29, 2008

Re: Twitter

O'Reilly likes it (Tim, of course, not Bill).

Tuesday, November 25, 2008

Much ado about nothing

Twitter is an enigma to me. It's a web and phone app that's almost degenerately simple: users post or text 'updates' of up to 140 characters and can subscribe to each other's updates. Apart from a bit of minor extra functionality ('nudges', for example), that's all there is to it. A few weeks ago, I decided to try Twitter after reading an interesting article on how it creates a social sixth sense (Clive Thompson, Wired). I only had two friends using the service back then, both techies. Most of the Twitter users I looked at were techies and, in particular, bloggers. At the same time, though, Twitter seemed like a pretty natural extension of normal texting. In my experience, lots of SMS are just like Twitter updates -- quick blurbs that people send to friends to let them know what's going on. Twitter is a fusion of blogging and texting. I wondered, then, whether its popularity would spread from the blogging crowd to the texting crowd -- middle school, high school, and college students.

Today I'm 'following' the Twitter feeds of seven of my friends from high school, all younger than me. I'm surprised by how fast this demographic shift seemed to happen, but I'm more surprised by how often some of my friends tweet. I clicked through to some friends' friends, some friends' friends' friends, and so on, to get an idea of what high-school twittering looked like. Some of the tweets were interesting. Most ranged from the mundane ("Meh. going to bed now") to the supremely self-referential ("I think that's a tweeting record for me!"). The people who use Twitter a lot are mostly replying to other people who Twitter a lot.

Does Twitter add value? It doesn't make money -- but does it add value for it's users? Can it really, as Clive Thompson says, allow social groups to be "more than the sum of their parts"? Maybe someday I'll experience one of those "amazing feats of social coordinaton". So far, though, the "tweets" I've seen are a lot like SuperPokes, pirate vs. ninja requests, "random musing" blog posts, FWD:fwd:Fwd:Fwd: funny cat!s and so much of the other stuff that's clogging the Tubes today (/b/, anyone?). They're yet another way for people to interactively waste each other's time. My question is: when and how will it end? Like, with a bang, or like Second Life, with a whimper?

Thursday, November 6, 2008

President Obama

This past weekend has been a blur. Some of my fellow students and I went to Las Vegas to help swing Nevada to Obama's side. We drove all day on Saturday; we worked on Sunday and Monday. I woke up at five on Election Day to put up door hangers, stayed up until one in the morning with the most energetic crowd I've ever seen, and woke up at five yesterday to fly back to California.

All the campaigning and partying, while fun, was on some level superficial. I got into some heated arguments with a junior in our group who seemed to be channeling Karl Marx, and into some more interesting arguments with other, more moderate fellow campaigners. For the most part, though, we focused on the very vague messages of "hope" and "change", and passed out policy fliers to the handful of people who wanted to know more. Nobody really asked the question of what America would become (or, now, will become) under an Obama presidency.

I've been looking for some good opinions. I thought that this article had an interesting take on it.

Like lots of what's been published since Election Day, it focuses pretty heavily on race. I'm more interested in what will happen to the economy. At least for the national debt, change seems like a good thing. Obama's tax plan has always bothered me, though.

Like most of us, I'll wait and see.

If there's one thing thats unambiguously good, it's that people care now. Lots of them who never voted before, voted this time. Students stopped ignoring politics. If you'd asked me just a few weeks ago, during New Student Orientation, what I thought about the next four years, I would have been gung-ho and pretty self-centered: Yes, Stanford will be fantastic. I'm still excited about the next four years, but like lots of other people I think about them in a broader way. What are we doing to help bring change?

Change is certainly here. Let's help make the transformation a great one.

Thursday, October 30, 2008

Waltzing cubes

Lucas, who I know from math and CS, has an absurd number of Rubik's cubes. He has the standard cubes in every size from 2x2 to 5x5. He has combinatorically ridiculous 7x7 cube that probably takes days to solve. He also has variations like square one. In a few weeks, he'll get a package from Japan and in it will be a void cube. (How you would build something like that without breaking the laws of physics is beyond me.)

Years ago, Lucas also made a Rubik's cube waltz. This means: he scripted and raytraced the whole animation in POV-RAY and Mathematica. Props!

Saturday, October 25, 2008

Flame wars

An old friend of mine isn't down with the Stanford Review. As he recently flamed:
Of course you know it all started with the Dartmouth Review. Those guys are just neo-con wannabes. So, isn't Anglo-Saxon free-market capitalism dead anyway?
Capitalism is dead? I'm not sold.


I don't think that Dartmouth, the proud home of Animal House, can be a values-upholding conservative flagbearer, either.

More seriously, though, I've found out that there are an incredible number of student-run periodicals here, and if I have time, I will write for one of them that isn't the Review.

My doubts about the Stanford Review were reinforced when I read their asinine article about Palin. Apparently "she can't lose". But I'm very optimistic that, as Hillary supporters used to say, "Yes She Can".

Busy two weeks

I've had a busy two weeks.

First, there was the trial-by-fire midterm week, where I and lots of my friends felt the difference between college and high school in a new, immediate way.

Then, there was the CS106X Boggle assignment, which I'll write more about soon.

There was also a Dave Brubeck concert. The 87-year-old jazz legend could barely walk, so he followed one of his bandmates in as if it were a congo line. He could barely talk, but his intro, filled with jazz inside-jokes, still got a lot of laughs. He then lowered himself onto the piano stool and played the most amazing two hours of jazz I've heard anyone play. It was beautiful. If his tour comes near where you live: don't miss it.

There was too much else to tell here, but no blog posts. That changes now.

Thursday, October 16, 2008

Happy Birthday!

to you.


Saturday, October 11, 2008


Here are two from a good friend of mine, from Seattle:

You have two ropes that burn in exactly 1 hour, but do not burn evenly (so half of the rope does not burn in 30 minutes). How do you measure a 45 minute time period by burning the ropes?

There are four kids on one side of a bridge with one flashlight and can cross in the times below:

Alex can cross the bridge in one minute
Bobby can cross the bridge in two minutes
Charlie can cross the bridge in five minutes
David can cross the bridge in ten minutes

If the kids can only cross one or two at a time, and must have the flashlight with them when they cross, how can all four get to the other side of the bridge in seventeen minutes?

Answer in the comments.
And in case you aren't thinking, SPOILER ALERT: answers will be in the comments.

Monday, October 6, 2008


It all began with ( one dictionary's plan to drop twenty-four obscure words from its definition of English.

Then, a friend with way too much time on his hands sympathized with these rare and endangered words, and took up their cause. I read his protest through one of Stanford's myriad mailing lists. It made my day.
As a staunch defender of all things prolix, I take exception to this list. Who doesn't need to indicate the condition of being a woman? I certainly do.

Indeed, it falls to students like us to negate the caducity of such words, to avoid that niddering and olid condition of the vocab naysayer. Why exuviate these treasures, when their fubsy substitutes can only embrangle our youth, and lead them to agrestic, willful ignorance?

No, I say we here commit to abstergent diction; eschew the caliginosity these fatidical rejections cast. Our linguistic librettos are our last periapts, our recourses against the oppugnant, the griseous malisons of the close-minded. When we write, when we speak, we must cast our votes for intelligibility and intelligence -- use these words so that their skirr in our pinnas is the roborant we are after.

So vote. Vote with your mouth. Vilipend these backward redacters with their own recrement. Now is not the hour for the mansuetude of muliebrity! Now is hour of nitid vaticination! To speak well, to honor our heritage in full -- this is not the impossible -- it is the compossible.

What else can I say? I've been nothing if not apodeictic.

Rob Ryan
Apparently, obscure words are like outermost planets. Nobody gives them a second thought -- until some committee decides that we don't need them anymore, at which point certain people take offense. Pluto was always a planet! Compossible was always a word! To the Don Quixotes of our world, they always will be.

I care, too, but in a much more worldly way. How could I pass up a chance for twenty-four Google keywords, however obscure, that are pretty much unique to me and Time?!

Sticking it to the Man

My classmate Ravi had a cool, but not neccesarily original idea. He wants to pay his $50,000 tuition in nickels, starting with the next ~$17,000 quarterly bill.

I love Stanford and if it was up to me, I wouldn't change anything -- except, of course, the tuition. Stanford's endowment grew by 23% to $17b last year, which means that they made about $200,000 for each student in every school. Most undergrads are on financial aid, but those who aren't pay more than $50K a year -- not a particularly large item on Stanford's balance sheet, but huge for a lot of the parents who write the checks.

And it's not just parents. Lots of us, especially grad students, leave with ridiculous debt loads. If I've gotten anything out of the market meltdown that we're in the middle of, it's that ridiculous debt loads are a bad idea.

Financial aid is difficult, too. Need-blind admission does a reasonable job of ensuring that everyone who gets in can come, but it doesn't guarantee fair treatment. At best, it lets smart kids without money or college degrees in their family come to Stanford and become seeds of change, close the poverty gap, and live happily ever after. At worst, it penalizes parents who work hard and save and subsidizes the ones who outspend their incomes.

If Ravi actually manages to wheel-barrow a million nickels to the Registar's Office, I'll be there, blogging the pictures and videos for you.

Saturday, October 4, 2008

Scavenger Hunt

I just got back from the annual freshman Scavenger Hunt. Part tour, part bonding event, and part hazing tradition, it was more fun than even I imagined.

Time-staggered by dorm to avoid gridlock, the 1600 took Caltrain into downtown San Francisco. We were preassigned to groups of about six freshman each, and there were far more groups than upperclass supervisors. They left us each with a sheet of tasks and the simple advice not to get arrested.

Some sample tasks:
  • Perform music theatre in front of the Opera House
  • Propose to a stranger. Bonus points for proposing to a stranger of the same sex (SF style).
  • Find a Cal student and convince him/her that you go to Cal and want to take a picture with him. Use your imagination.
  • Shake a stranger's hand through the fly of your pants.
There were about a hundred tasks in this vein.

We named our group the Golden Bears, referencing the Cal mascot as a way of explaining to the public who we were and why we were so blatantly disturbing the peace. We stood out.

Immature? Definitely.

Still, there is a serious side to Scavenger Hunt, and I think it's a great tradition.
It introduced all the new students to the diversity and irreverence of San Francisco, and gave them opportunity to participate. For some of the international students and those from rural America, I'm guessing that today was a major eye-opener.

Today's fun was also a refreshing break from Stanford's sometimes maddeningly bureaucratic administration. An event this big has got to be planned by the Admins with the uppercase A. It's nice to know that they not only tolerate, but encourage freedom of choice, even in cases like this where our choices are probably embarassing or uncomfortable for them.

Finally, Scavenger Hunt pushed people past their comfort zone and made everyone think about the things we consider right and wrong, acceptable and taboo. Do our unwritten rules make sense? What happens when they're broken? What happens when people disagree on where to draw the line?

And the kicker? LoveFest is going on right now in SF. There are whole city blocks where naked people compete with assless chaps for attention and the pot smoke hangs thicker than the fog. The frosh kids who went that route stood out, too -- for conforming too much to society's norms.

Friday, October 3, 2008

President Palin

Matt Damon had a some thoughts on the danger of Palin becoming President in a recent interview.

Then, yesterday, Palin spoke her mind on education.

Say it ain't so, Joe, there you go again pointing backwards again. You preferenced your whole comment with the Bush administration. Now doggone it, let's look ahead and tell Americans what we have to plan to do for them in the future. You mentioned education and I'm glad you did. I know education you are passionate about with your wife being a teacher for 30 years, and god bless her. Her reward is in heaven, right?

(From the CNN transcript of the VP debate.)

Later in the debate, both running mates discussed the possibility of taking over if the president died.

If McCain wins, he'll be the oldest president ever to take office. If he doesn't make it to 2012, Palin will lead the free world in his stead. Scary? Yes. Embarassing? Even more so...

Vote for change.

Tuesday, September 30, 2008

Putnam math competition

This is really cool. Tonight, I joined the kids here who will give this math test a shot in a few months. We had an overflow crowd at our first meeting.

The professor who's teaching us the ropes in weekly sessions is a great guy.

Here's one problem I did, from the promo poster:

Find the smallest natural number n which has the following properties:
(i) its decimal representation has a 6 as its last digit, and
(ii) if the last digit 6 is erased and placed in front of the remaining digits, the resulting number is four times as large as the original number n.

If n starts with 6, and n = 4k, then k must start with a 1. So:

n = 61 ..,

k = 1 ... 6

Now the cool part: some recursive long multiplication.

Multiplying 6*4 gives you 24, so 4 is the last digit of n. This means that 4 is also the second-to last digit of k. So 4*4 +2 = 18. 8 is the second-to-last digit of n, and third-to-last digit of k. We know that 1 is the second digit of n, so eventually, we have to get to a 1.





This is true. So I think that 153846 is the smallest n that ends in 6 where shifting the digits right gives you 4n.
I love this stuff.

My badass advisor

My academic advisor, I am glad to announce, is John C Bravman.

Not only is he my advisor, he is also the dean of my dorm complex, FroSoCo (”freshman sophomore college”, in true Stanford alphabet-soup style). Almost a decade ago, a prospective student wrote him a letter, asking him some questions about Stanford and addressing him as a “badass dean”. He later referenced this letter in a speech, and inadvertently gave himself a new title.

Today, Bravman is the Vice Provost of Undergraduate Education: the top-ranked suit in the undergraduate college. Whenever he walks out to address the student body in the Memorial Auditorium, my FroSoCo buddies and I chant “B-A-D… B-A-D… B-A-D…”, which stands for: “badass dean”. It has a nice ring to it, especially in the awesome acoustic environment of MemAud.

Mr. Bravman lives up to his badass name. He throws FroSoCo barbeques every Friday, hosts really interesting speakers at his house across the street on a roughly biweekly basis, and maintains a gigantic DVD collection that students can borrow from.

This is how I and four of my friends came to have Stanford’s one and only badass advisor. Once again, I can’t believe my luck.

Hello world

This is my first real blog. I started my freshman year at Stanford a week ago today, and it’s been fantastic. There are too many great things to do and not enough hours in a day to do them. So much is going on, in fact, that I think it’s high time for me to write a blog.

I’ll write about Stanford, about programming, about math, and about whatever looks fun or interesting to me.