From nobody@cs.Buffalo.EDU Fri Jul 18 16:55 EDT 1997 From: nobody@cs.Buffalo.EDU Date: Fri, 18 Jul 1997 16:55:32 -0400 (EDT) To: techreps@cs.Buffalo.EDU Subject: techrep: POST request Content-Type: text Content-Length: 1259 Comments: bach ContactPerson: cai@cs.buffalo.edu Remote host: bach.cs.buffalo.edu Remote ident: cai ### Begin Citation ### Do not delete this line ### %R 97-10 %U rubs.ps %A Cai, Jin-Yi %A Nerurkar, Ajay %A Wu, Min-You %T The Design of Uncheatable Benchmarks Using Complexity Theory %D July 18, 1997 %I Department of Computer Science, SUNY Buffalo %K benchmarks, complexity theory %X We study uncheatable benchamrks. We present some schemes of their design and implementations. We present two methods to obtain computational advantage in judging performance results. In the first approach, the tester gains a computational advantage via a hidden ``secret,'' which is randomly generated. With the secret information, the tester can know, or can easily compute, the correct answer in advance. This approach is called the Secret Key (SK) method. Secondly, for many problems, verifying the result is easier than computing it. For example, verifying the result of a linear equation solver can be accomplished faster than any known algorithm which computes it. This asymmetry allows the tester an computational advantage over the vendor. This approach is called the Result Verification (RV) method.