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.

  • 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$ Oct 27, 2010 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, 2010 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$ Oct 27, 2010 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$ Oct 28, 2010 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, 2010 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.