20
votes
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 ...
- 7,175
20
votes
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")...
- 7,175
16
votes
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 ...
- 8,546
16
votes
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 ...
- 14.2k
13
votes
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 ...
- 131
12
votes
$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 ...
- 5,290
11
votes
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 ...
- 3,478
11
votes
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 ...
- 8,546
10
votes
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 ...
- 36.4k
10
votes
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 ...
- 4,440
10
votes
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 ...
- 36.4k
9
votes
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}$ ...
- 8,801
8
votes
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 ...
- 36.4k
8
votes
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 ...
- 181
8
votes
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 [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ ...
- 36.4k
7
votes
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 ...
- 1,419
7
votes
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 ...
- 548
7
votes
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 ...
- 15.6k
6
votes
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 ...
- 2,838
6
votes
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. ...
- 50.6k
6
votes
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 ...
- 15.6k
6
votes
Accepted
Why should we believe that $NEXP \not \subset P/poly$
The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $...
- 12.6k
6
votes
Why should we believe that $NEXP \not \subset P/poly$
Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ ...
- 1,566
4
votes
Accepted
Efficient randomness reduction using k-wise independence
Yes. You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree $...
- 11.3k
3
votes
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
- 131
3
votes
Can we construct a k-wise independent permutation on [n] using only constant time and space?
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 ...
- 11.3k
3
votes
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL}...
- 1,733
3
votes
Adleman's theorem over infinite semirings?
This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while ...
- 1,419
3
votes
Accepted
From $PIT\in P$ to $P=BPP$
If PIT over a finite field $F$ is in P, then there is a family of multilinear polynomials whose graph is decidable in $\mathsf{NE}$ but which does not have poly-size $F$-algebraic circuits (Carmosino-...
- 36.4k
3
votes
Accepted
What do stronger circuit lower bounds give in terms of derandomization?
It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$ then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590).
(Actually, a ...
- 5,290
Only top scored, non community-wiki answers of a minimum length are eligible