Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-149 | 7th December 2006 00:00

The Complexity of Forecast Testing

RSS-Feed




TR06-149
Authors: Lance Fortnow, Rakesh Vohra
Publication: 11th December 2006 10:00
Downloads: 3157
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint