Category Archives: people

commentary, computer science, gambling, people, prediction markets, trends

Where is the betting market for P=NP when you need it?

12 Comments

HP research scientist Vinay Deolalikar has constructed the most credible proof yet of the most important open question in computer science. If his proof is validated (and there are extremely confident skeptics as you’ll see) he proved that P≠NP, or loosely speaking that some of the most widespread computational problems — everything from finding a good layout of circuits on a chip to solving Sudoku puzzles to computing LMSR prices in a combinatorial market — cannot be solved efficiently. Most computer scientists believe that P≠NP, but after decades of some of the smartest people in the world trying, and despite the promise of worldwide accolades and a cool $1 million from the Clay Mathematics Institute, no one has been able to prove it, until possibly now.

Scott Aaronson is a skeptic, to say the least. He made an amazing public bet to demonstrate his confidence. He pledged that if Deolalikar wins the $1 million prize, Aaronson will top it off with $200,000 of own money. Even more amazing: Aaronson made the bet without even reading the proof. [Update: I should have said “without reading the proof in detail”: see comments] (Perhaps more amazing still: a PC World journalist characterized Aaronson’s stance as “noncommittal” without a drip of sarcasm.) [Hat tip to Dan Reeves.]

As Aaronson explains:

The point is this: I really, really doubt that Deolalikar’s proof will stand. And while I haven’t studied his long, interesting paper and pinpointed the irreparable flaw… I have a way of stating my prediction that no reasonable person could hold against me: I’ve literally bet my house on it.

Aaronson is effectively offering infinite odds [Update: actually more like 2000/1 odds: see comments] that the question “P=NP?” will not be resolved in the near future. Kevin McCurley and Ron Fagin made a different (conditional) bet: Fagin offered 5/1 odds (at much lower stakes) that if the question is resolved in 2010, the answer will be P≠NP. Bill Gasarch says that he, like Aaronson, would bet that the proof is wrong… if only he were a betting man. Richard Lipton recounts a discussion about the odds of P=NP with Ken Steiglitz.

But beyond a few one-off bets and declarations, where is the central market where I can bet on P=NP? I don’t even necessarily want in on the action, I just want the odds. (Really!)

My first thought was the Foresight Exchange. It does list one related contract — Good 3SAT Algorithm by 2020 — which should presumably go to zero if Deolalikar’s proof is correct. It hasn’t budged much, consistent with skepticism (or with apathy). My second thought was the PopSci Predictions Exchange (PPX), though sadly it has retired. InklingMarkets has a poll about whether P=NP will be resolved before the other Clay Institute prize questions, but not about how it will be resolved or the odds of it happening. (The poll is one of several markets sponsored by the Woodrow Wilson Center’s Science and Technology Innovation Program — hat tip to Vince Conitzer.) I don’t see anything at longbets, and anyway longbets doesn’t provide odds despite it’s name.

In 1990 Robin Hanson provocatively asked: Could gambling save science?. That question and his thoughtful answers inspired a number of people, including me, to study prediction markets. Indeed, the Foresight Exchange was built largely in his image. P=NP seems one of the most natural claims for any scitech prediction market.

All these years later, when I really need my fix, I can’t seem to get it!

2010/08/14 Update: Smarkets comes the closest: they have real-money betting on whether P=NP will be resolved before the other Clay Institute prize questions. They report a 53% chance as of 2010/08/14 (for the record, I would bet against that). What’s missing is when the award might happen and how the question might be resolved, P=NP or P≠NP. I also don’t see a graph to check whether Deolalikar’s proof had any effect.

If it wasn’t clear in my original post, I found Aaronson’s bet incredibly useful and I am thrilled he did it. I believe he should be commended: his bet was exactly what more scientists should do. Scientists should express their opinion, and betting is a clear, credible, and quantitative way to express it. It would be as shame if some of the negative reactions caused him or others not to make similar bets in the future.

I just wish there were a central place to make bets on scientific claims and follow the odds in the vision of Robin Hanson, rather than every scientist having to declare their bet on their own individual blogs.

fun, people, probability, technology, trends

The most prescient footnote ever

25 Comments

Back in 2004, who could have imagined Apple’s astonishing rise to overtake Microsoft as the most valuable tech company in the world?

At least one person.

Paul Graham wins the award for the most prescient parenthetical statement inside a footnote ever.

In footnote 14 of Chapter 5 (p. 228) of Graham’s classic Hackers and Painters, published in 2004, Graham asks “If the the Mac was so great why did it lose?”. His explanation ends with this caveat, in parentheses:

And it hasn’t lost yet. If Apple were to grow the iPod into a cell phone with a web browser, Microsoft would be in big trouble.

Wow. Count me impressed.

To find this quote, search inside the book for “ipod cell”.

To get into a 2004 midset, look here and here.

commentary, people, politics, yahoo

2 weeks, 2 geeks: My two new fearless leaders

2 Comments

Well, geeks are certainly inheriting my earth.

On January 13, my company named Carol Bartz, a self-avowed math nerd and former punch-card carrying member of her college computer club, as its CEO. In her own words:

I was a real nerd. I love, love, love, love math. Back in the late ’60s, math meant being a teacher if you were a woman. I wasn’t interested in teaching. Then I took my first computer course. It was crazy. It was like math, only more fun. I switched to computer science.

Exactly one week later, on January 20, my country turned over executive control to Barack Obama, a CrackBerry addicted comic book geek. In his inauguration speech, Obama vowed to “restore science to its rightful place”, “wield technology’s wonders”, and even addressed “non-believers” — wording that in any sane universe should be entirely unremarkable, yet in ours appears to represent an unprecedented milestone.

I can’t recall a two-week span filled with so much geek pride and cautious optimism.

Back to the Carol Bartz quote. Reading it brings a smile to my face. It also reminds me of my mom, who, convinced it was her only option, taught middle school for a few years before returning to medical school to pursue her passion, enjoying a successful career as one of the first women radiologists.

I highly recommend Bartz’s essay, which mixes biography with prescience and insight. Bartz describes how technology and the Internet are transforming collaboration and improving productivity, at the same time ushering in an era of information overload, email bankruptcy, and misuse of the extra time technology affords. Remarkably, she wrote about these things in 1997!

It’s amazing to think how things have changed since 1997. My own first web experience, courtesy Mosaic, came in 1994, the same year Yahoo! was founded. In 1996, PayPal predecessor and public company First Virtual wrote their own keystroke-sniffing malware as a stunt to bolster their urgent call to “NEVER TYPE YOUR CREDIT CARD NUMBER INTO A COMPUTER”. Ebay was founded in 1995, PayPal in 1998. In 1997, Friendster had neither come nor gone, and Facebook CEO Mark Zuckerberg was 13.

Yet Bartz’s words seem more relevant than ever today.

artificial intelligence, people

Death in artificial intelligence

1 Comment

Until just reading about it in Wired, I knew little1 of the apparent suicide of Push Singh, a rising star in the field of artificial intelligence.

Singh seemed to have everything going for him: brilliant and driven, he became the protégé of his childhood hero Marvin Minsky, eventually earning a faculty position alongside him at MIT. Professionally, Singh earned praise from everyone from IEEE Intelligent Systems, who named Singh one of AI’s Ten to Watch (apparently revised), to Bill Gates, who asked Singh to keep him appraised of his latest publications. Singh’s social life seemed healthy and happy. The article struggles to uncover a hint of why Singh would take his own life, mentioning his excruciating chronic back pain (and linking it to a passage on the evolutionary explanation of pain as “programming bug” in Minsky’s new book, a book partly inspired by Singh).

The article weaves Push’s story with the remarkable parallel life and death of Chris McKinstry, a man with similar lofty goals of solving general AI, and even a similar approach of eliciting common sense facts from the public. (McKinstry’s Mindpixel predated Singh’s OpenMind initiative.) McKinstry’s path was less socially revered, and he seemed on a never ending and aching quest for credibility. The article muses whether there might be some direct or indirect correlation between the eerily similar suicides of the two men, even down to their methods.

For me, the story felt especially poignant, as growing up I was nourished on nearly the same computer geek diet as Singh: Vic 20, Apple II, Star Trek, D&D, HAL 9000, etc. In Singh I saw a smarter and more determined version of myself. Like many, I dreamt of solved AI, and of solving AI, even at one point wondering if a neural network trained on yes/no questions might suffice, the framework proposed by McKinstry. My Ph.D. is in artificial intelligence, though like most AI researchers my work is far removed from the quest for general AI. Over the years, I’ve become at once disillusioned with the dream2 and, hypocritically, upset that so many in the field have abandoned the dream in pursuit of a fractured set of niche problems with questionable relevance to whole.

Increasingly, researchers are calling for a return to the grand challenge of general AI. It’s sad that Singh, one of the few people with a legitimate shot at leading the way, is now gone.

Push Singh Memorial Fund

1Apparently details about Singh’s death have been slow to emerge, with MIT staying mostly quiet, for example not discussing the cause of death and taking down a memorial wiki built for Singh.
1 My colleague Fei Sha, a new father, put it nicely, saying he is “constantly amazed by the abilities of children to learn and adapt and is losing bit by bit his confidence in the romantic notion of artificial intelligence”.