[Computational Complexity] My Publications
- I spent some time this weekend updating my publications page. I did well in the summer conference season: An ICALP paper and two each in Complexity and TARK. Not to mention my first ever Algorithmica paper was just accepted for publication.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.
Posted By Lance to Computational Complexity at 5/05/2009 05:51:00 AM