Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [random-oracles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
21 votes
2 answers

For a random oracle R, does BPP equal the set of computable languages in P^R?

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a ...
Scott Aaronson's user avatar
9 votes
1 answer

Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
user avatar
7 votes
1 answer

"Largest" class properly contained in PSPACE for a random oracle

Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly ...
Alessandro Cosentino's user avatar
7 votes
2 answers

What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$. I wanted to know if there are more examples like this.
Mal's user avatar
  • 355
6 votes
1 answer

What are alternatives to the random oracle model for modelling hash functions?

I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as ...
RDN's user avatar
  • 325
5 votes
1 answer

Is $UP\not=NP$ with respect to random oracle?

It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite. Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\...
Turbo's user avatar
  • 12.9k
4 votes
0 answers

A natural result that relativized to a random oracle is true with probability 1/2

There are several well known results regarding random oracles, e.g. $\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles. Are there any known natural examples where a similar statement ...
Kaveh's user avatar
  • 21.7k
3 votes
1 answer

Almost-P and related definitions

I'm pretty sure this has a trivial answer but it's always faster to ask the community :-) I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "...
Mahdi Cheraghchi's user avatar
3 votes
0 answers

Invertible function with hard to find collisions in the Random Oracle Model

This question is inspired by this tweet. I discussed this with some people at my institution when this came out and came to the conclusion that this was probably possible using lattice-based ...
Bolton Bailey's user avatar
3 votes
0 answers

Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$

I have a black-box function which returns true with probability $ P(A) $, that I don't know how to calculate. I receive evidence B, and I want to create a function which returns true with probability $...
Command Master's user avatar
2 votes
0 answers

Impossibility of uniform generation in random world

I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers. I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich ...
Pur2all's user avatar
  • 21
1 vote
2 answers

Is true randomness and the physical Church-Turing thesis incompatible?

As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
Christopher King's user avatar
1 vote
0 answers

How can ORAMs be secure in the random oracle model with O(1) protected words of O(lg n) bits each?

This post assumes some knowledge about ORAMs on the reader's part. Very roughly, ORAMs are ways in which one can simulate a generic RAM program for $n$ steps in such a way that the memory access ...
Anonymous's user avatar
  • 101
1 vote
0 answers

The meaning of separations in cryptography

From the paper of Impagliazzo and Rudich "Limits on the Provable Consequences of One-Way Permutations": We provide strong evidence that it will be difficult to prove that secure secret agreement is ...
user34219's user avatar