3
$\begingroup$

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have specifically considered applying oracles to decision problems in some specific domain/field. I am just looking for general pointers and do not have a specific domain in mind.

$\endgroup$
  • 1
    $\begingroup$ hardware verification effectively uses SAT as an oracle, since there are efficient SAT solvers. I'm not sure if this is what you're looking for though $\endgroup$ – Suresh Venkat Oct 27 '10 at 4:53
  • $\begingroup$ Thanks Suresh, i did not know about h/w verification: but thats not the kind i was looking for $\endgroup$ – kryptos Oct 27 '10 at 14:22
  • 2
    $\begingroup$ If you consider a common coin randomized consensus algorithm, all parties have access to an oracle, which at each round of the protocol reads either 0 or 1, with some probability, to all the parties who read it during that round. The next round the value is changed randomly again. One ref. might be "Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems (2005, R Friedman, A Mostefaoui, M Raynal)" $\endgroup$ – M. Alaggan Oct 27 '10 at 21:34
  • 1
    $\begingroup$ Many worst case analysis is done as a game played against an all powerful adversary; that is, an oracle. I think this is even more explicit in the analysis of some online algorithms. $\endgroup$ – Sariel Har-Peled Oct 28 '10 at 17:03
  • $\begingroup$ @M.Allagan: Thanks, that is something along the lines i was looking for, i will read the paper in more detail to understand $\endgroup$ – kryptos Nov 10 '10 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.