The Complexity of Forecast Testing

DOI10.3982/ECTA7163zbMath1160.91396MaRDI QIDQ3627277

Rakesh V. Vohra, Lance J. Fortnow

Publication date: 18 May 2009

Published in: Econometrica (Search for Journal in Brave)

zbMATH Keywords

prediction; bounded rationality; forecast testing

Mathematics Subject Classification ID

62G10: Nonparametric hypothesis testing

62M09: Non-Markovian processes: estimation

62P30: Applications of statistics in engineering and industry; control charts

91B82: Statistical methods; economic indices and measures

91A26: Rationality and learning in game theory

60G25: Prediction theory (aspects of stochastic processes)

Related Items

On the degree of univariate polynomials over the integers, High-confidence predictions under adversarial uncertainty, Quantum rejection sampling, Compressed matrix multiplication, Testing theories with learnable and predictive representations, Nonmanipulable Bayesian testing, On universal algorithms for adaptive forecasting, A nonmanipulable test, On comparison of experts, Merging and testing opinions, Learning hurdles for sleeping experts, Restriction access, Mechanism design with approximate valuations, Quantum strategic game theory, The curse of simultaneity, No justified complaints, From randomizing polynomials to parallel algorithms, Practical verified computation with streaming interactive proofs, Paging for multi-core shared caches, Noise vs computational intractability in dynamics, Distribution free evolvability of polynomial functions over all convex loss functions, Algorithms on evolving graphs, Towards deterministic tree code constructions, Linear time decoding of regular expander codes, List decoding subspace codes from insertions and deletions, Bounds on locally testable codes with unique tests, Approximately optimal mechanism design via differential privacy, Fairness through awareness, Dynamics of prisoner's dilemma and the evolution of cooperation on networks, Crowdsourced Bayesian auctions, Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure, Quantum interactive proofs with weak error bounds, Quantum money from knots, (Leveled) fully homomorphic encryption without bootstrapping, From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, Targeted malleability, Sherali-Adams relaxations and indistinguishability in counting logics, Graph densification, Spectral sparsification via random spanners, Multicommodity flows and cuts in polymatroidal networks, On persistent homotopy, knotted complexes and the Alexander module, Gadgets and anti-gadgets leading to a complexity dichotomy, On beating the hybrid argument, Linear programming, width-1 CSPs, and robust satisfaction, Marginal hitting sets imply super-polynomial lower bounds for permanent