<p>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.</p>

CC BY-SA 3.0
2013-05-02T21:38:33.500Z
I assume you know about natural proofs, relativizing vs non-relativizing proofs, and the like?  That line of work shows that certain kinds of proofs will never be able to prove that $P \ne NP$ (for instance), and those kinds of proofs can be characterized because they relativize: they remain valid with respect to an arbitrary oracle.
D.W.
CC BY-SA 2.5
2010-10-27T04:53:37.263Z
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
Suresh Venkat
CC BY-SA 2.5
2010-10-27T14:22:13.767Z
Thanks Suresh, i did not know about h/w verification: but thats not the kind i was looking for
kryptos
CC BY-SA 2.5
2010-10-27T21:34:12.783Z
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)"
Mohammad Alaggan
CC BY-SA 2.5
2010-10-28T17:03:52.590Z
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.
Sariel Har-Peled
CC BY-SA 2.5
2010-11-10T15:10:20.013Z
@M.Allagan: Thanks, that is something along the lines i was looking for, i will read the paper in more detail to understand
kryptos
<cc.complexity-theory><reference-request><computability><oracles>
Reference Request: Oracle applications outside cryptography
kryptos
# Reference Request: Oracle applications outside cryptography

(Asked by: username_0 on 2010-10-26)

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.

**Tags:** cc.complexity-theory, reference-request, computability, oracles

> **Comments:**
> **username_2**: 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  
> **username_0**: Thanks Suresh, i did not know about h/w verification: but thats not the kind i was looking for  
> **username_3**: 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)"  
> **username_4**: 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.  
> **username_0**: @M.Allagan: Thanks, that is something along the lines i was looking for, i will read the paper in more detail to understand  
> **username_1**: I assume you know about natural proofs, relativizing vs non-relativizing proofs, and the like?  That line of work shows that certain kinds of proofs will never be able to prove that $P \ne NP$ (for instance), and those kinds of proofs can be characterized because they relativize: they remain valid with respect to an arbitrary oracle.  

---

## 0 answers

