# Tag Info

Accepted

### Is BPP vs. P a real problem after we know BPP lies in P/poly?

Not sure how much of an answer this is, I'm just indulging in some rumination. Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the ...

### Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...

### Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
Accepted

### What is worst case complexity of number field sieve?

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's ...

### Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...

### $BPL$ with polylog random bits is in $L$

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
Accepted

### Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

Suppose you have a circuit which takes as input an advice string and a random string. (So this circuit would be in $BPP/Poly$ or something like that.) You can convert this into a purely deterministic ...

### More on PH in PP?

By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is ...
Accepted

### Connections between Graph Isomorphism and Polynomial Equivalence

The paper you linked in the comments - and references therein - already seems to answer your first question. For your second question: I have little reason to think that there is a theorem of the ...

### On derandomizing polynomial identity testing

[tl;dr] A lot is known, and it is a very active area! [/tl;dr] It is important to specify the representation of the input ...
Accepted

### If $P=BPP$, then Is it correct that $IP=NP$?

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context ...
Accepted

### When does randomization stops helping within PSPACE

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ ...
Accepted

### Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

Since PIT is in $\mathsf{coRP}$, if there is no efficient derandomization then $\mathsf{P} \neq \mathsf{RP}$ (and, in particular, $\mathsf{P} \neq \mathsf{NP}$, but that's not so surprising, since we ...

### What is worst case complexity of number field sieve?

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the ...
Accepted

### Randomized algorithms not based on Schwartz-Zippel

Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, Problem 2.6 of : Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ ...

### Is it known whether $BPP\cap NP\subseteq RP$?

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which ...
Accepted

### Implications of faster randomized $CIRCUIT SAT$ algorithm

The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the ...

### Randomized algorithms not based on Schwartz-Zippel

This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no ...
Accepted

### Uniform derandomisation of circuit complexity classes

The class uniform-RNC has been studied a lot. It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and ...

### Minimum weights needed to derandomize weight assignment by isolation lemma

A deterministic scheme with tiny weights is easy to achieve: first, compute an arbitrary perfect matching, deterministically. Then, give the matched edges weight zero and all other edges weight one. ...
Accepted

### Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
Accepted

### Efficient and simple randomized algorithms where determinism is difficult

Finding square roots modulo prime number: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
If you are willing to use cryptographic techniques and rely upon cryptographic assumptions and to accept a computational notion of $k$-wise independence, it's posible that format-preserving encryption ...