Uncheatable Benchmarks Using Numerical Instability

Abstract:

We present the first practical {em reliable/} benchmark.
This benchmark is ``uncheatable'', in the sense that one can not
substantiate a claim to have obtained the results of its computation
without actually doing so. In addition to having the ability to check
the computation results for correctness, they are known to require
at least some (specified) computation time to be computed.
Initial work in trying to provide for reliability in benchmark is
presented in cite{CLSY}. They rely on cryptographic assumptions for
the reliability feature in the benchmarks they propose.
Our benchmarks are based on numerical instability of some matrix
computations, and are therefore very similar to benchmarks actually in
use, with the added benefit of reliability.