The Complexity of Forecast Testing

Joint Theory-STIET Seminar
Consider a weather forecaster predicting a probability of rain for the
next day. We consider tests that given a finite sequence of forecast
predictions and outcomes will either pass or fail the forecaster.
Sandroni (2003) shows that for any test that passes a forecaster that
knows the distribution of nature can be probabilistically passed by a
forecaster that has no knowledge of future events.

We look at how complex the forecaster needs to be to pass the tests. A
good tester is one that passes the truth, i.e., any forecaster that
gives the true probabilities of future events will pass the test with
high probability. An ignorant forecaster bases his predictions solely
on previous outcomes. We show
1) For any reasonable time-bound t(n), there are good testers that run
in time t^2(n) that will fail with high probability all ignorant
forecasters running in time t(n) for a specific distribution.
2) We create a linear-time good tester and such that any ignorant
forecaster that passes the test with high probability on all
distributions can be used to factor arbitrary integers efficiently.
3) We extend the previous result so that any ignorant forecaster can
solve arbitrary NP search problems like traveling salesperson and
graph coloring and even PSPACE-hard problems like playing a perfect
game of chess on an arbitrary size board.

Joint work with Rakesh Vohra (Northwestern/Kellogg)

Homepage: http://people.cs.uchicago.edu/~fortnow/

Lance Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989
and has spent his academic career in Computer Science at the
University of Chicago with the exception of a senior research
scientist position at the NEC Research Institute from 1999-2003. In
1992 he received the NSF Presidential Faculty Fellowship and was a
Fulbright Scholar visiting CWI in Amsterdam 1996-97. Fortnow studies
computational complexity and its applications to electronic commerce,
quantum computation, bioinformatics, learning theory and cryptography.
Fortnow also writes the popular scientific and academic weblog
Computational Complexity (http://weblog.fortnow.com)