#### Other Event

# 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)