Gas station without pumps

2011 October 29

DARPA Shredder Challenge

Filed under: Uncategorized — gasstationwithoutpumps @ 09:50
Tags: , , ,

The Defense Advanced Research Projects Agency wants to improve spycraft by making it easier to reconstruct shredded documents automatically: DARPA Shredder Challenge. The puzzle itself is mildly interesting: reassembling scanned images of shredded documents is not a trivial problem, but for small enough problems some simple brute-force approaches look like they could be used.  Bootstrapping those approaches to larger problems is an interesting challenge that may best be solved by huge computing resources like Google has.  There are obvious applications in archæology and for banks and businesses that mistakenly shred important documents, as well as the spycraft that DARPA cares about.

But DARPA are not willing to spend any money to achieve this goal, so they are attempting a prize competition.  This has worked well for them in the past (with the autonomous vehicle challenge) and it worked for Netflix (improving their movie recommender), but I think that this time DARPA has gone too far in the cheapskate direction.  This time they are offering only a $50,000 prize. That will pay for one grad student or postdoc for a year—if you win.  It probably wouldn’t even pay for the computer time needed to solve the biggest problems. Even Netflix, with a simpler problem, knew enough to offer a million dollar prize.

They may get a few hobbyists or students interested in the problem, but is unlikely to interest many professionals—the low odds of winning combined with the tiny prize make the expected value of entering the contest too low to invest more than a few hours in.  Perhaps they think that there is a system already out there (perhaps hidden in one of the government’s many secret agencies), but not advertised, and they are just trying to get their hands on it. $50k may be just enough to bribe a low-level flunky to release something illicitly (I wouldn’t know, having never bribed anyone and never been offered a bribe), but it isn’t enough to fuel development.



  1. I forget which competition it was, perhaps one of the previous few SIGKDDs, where one of the top teams won using just a laptop while everybody else was throwing huge clusters at the problem. My point is that the small prize might be imposing a constraint on computing power that might actually help the teams come up with clever algorithmic techniques. Not sure if this is what DARPA intended because as you point out, they might just be cheapskates. But it’s possible this might even work out well.

    Comment by Pramod — 2011 October 29 @ 10:31 | Reply

  2. The results for the challenge have been announced:

    I briefly skimmed the results, and the teams seem to have done surprisingly well.

    Comment by Pramod — 2011 December 3 @ 21:34 | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: