ECCC-Report TR06-149https://eccc.weizmann.ac.il/report/2006/149Comments and Revisions published for TR06-149en-usMon, 11 Dec 2006 10:00:23 +0200
Paper TR06-149
| The Complexity of Forecast Testing |
Lance Fortnow,
Rakesh Vohra
https://eccc.weizmann.ac.il/report/2006/149Consider 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 any test which passes a
forecaster who knows the distribution of nature, can be
probabilistically passed by a forecaster with no knowledge of
future events.
We look at the computational complexity of such forecasters and
exhibit a linear-time test and a distribution of nature such that
any forecaster without knowledge of the future that can fool the
test must be able to solve PSPACE-hard problems by requiring the
forecaster to simulate a prover in an arbitrary interactive proof
system.
Mon, 11 Dec 2006 10:00:23 +0200https://eccc.weizmann.ac.il/report/2006/149