My proudest 2009 publication: The Complexity of Forecast Testing written with Rakesh Vohra that appeared in the January issue of Econometrica, generally considered the top journal in economic theory. Consider the problem of testing a forecaster (like a weatherperson) who give a probability each day of an even that happens the next day. Alvaro Sandroni proved a strong negative result: Suppose a tester T makes decisions in a finite number of steps and passes (with high probability) any forecaster that correctly predicts nature. Then there is a probabilistic forecaster that will, with high probability, pass test T without any knowledge of nature, even if nature is adversarial.
Sandroni's forecaster requires solving exponential-sized linear programs. Vohra and I showed that Sandroni's theorem doesn't hold if we limit both the tester and forecaster to be efficiently computable (under generally believed hardness assumptions). We created efficiently computable testers so that for some distributions for nature, a forecaster would have to factor numbers or solve PSPACE-hard problems to pass the test.
This paper represents a large part of my current research: Applying the ideas and tools of computational complexity to economic theory, in particular seeing what happens in a wide variety of economic models with when we require the agents to be computationally efficient. Given the success of this paper (and others), perhaps some economists are beginning to realize the importance of capturing computation costs in their models.
congratulations, lance.
ReplyDeleteI did well in the summer conference season: An ICALP paper and two each in Complexity and TARK.I don't want to be a spoil-sport here, but these kind of statements from relatively senior people in TCS can lead to graduate students to stress quantity over quality which has become the bane of TCS these days (cf. Koblitz's famous conjecture (2008) regarding n papers in one yr vs. one paper in n years). It would be much more preferable to say that "I proved several interesting theorems this summer, and this is why they are interesting ..." rather than stress where these papers have been accepted to be presented, as if the acceptances themselves are a certificate of some sort.
ReplyDeleteAnon 2: while this was his opening sentence -- a way of advertising his wares, as it were -- the bulk of Lance's post IS on a single result that he finds his most interesting recent work. And it ends with an overview of what he thinks is the interesting CLASS of problems he's working on. I don't think his post stresses quantity over quality by any means.
ReplyDeleteAnd congratulations, Lance...
I second anon 2 in that I found
ReplyDeletethe emphasis on paper acceptances
and numbers a bit off-putting.
For most of the papers mentioned, we are not given an idea of the contents, just the "pedigree" of the results. So I agree that this gives the wrong idea. Why not have a post about each paper giving us the main theorems/ideas a la David Eppstein and his recent papers? That would be really interesting and not so "smug".
ReplyDeleteThe researchers in economic theory believed those complexity assumptions! They must have good faith on us.
ReplyDeleteUgh! What's with the sniping, Anons?
ReplyDeleteCongratulations, Lance. I look forward to reading your Econ paper... soon after I'm done reading the obligatory several dozen FOCS submissions.
- Amit C