20

$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") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$. The idea is that you can think of a randomized ...


17

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 result would be the big breakthrough more so than the conclusion itself. For Question 2 I want to share some background and a thought. Pretty much all the ...


16

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 factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ...


16

Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.


16

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 Kabanets show that PIT in P would imply some circuit lower bounds. So circuit lower bounds are the only reason (but a pretty good one) that we believe P = BPP.


13

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 a graph. There is a randomized poly-time algorithm to approximate these numbers within a (1+eps) factor, whereas the best deterministic algorithms achieve only ...


13

If you're asking for independent problems, how about: Find a prime in the interval $[N, 5N/4]$, Find two primes whose product is in the interval $[N, 9N/8]$, Find three primes whose product is in the interval $[N, 17N/16]$, Find four primes whose product is in the interval $[N, 33N/32]$, Find five primes whose product is in the interval $[N, 65N/...


12

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 decreased to $O(S)$. In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can ...


11

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 circuit, which takes a somewhat larger advice string, as follows. There are $2^n$ possible inputs. By hypothesis about the circuit, each random string is good ...


10

[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 polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case ...


10

There is a particular use of randomness that is fairly common in parameterized complexity, which involves either the isolation lemma, or the Schwartz-Zippel lemma. Roughly, it involves defining a large enumeration of potential solutions, and arguing that all non-solutions "pair up" (e.g., are counted twice) while the desired solution(s) are counted only once....


10

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 not in PP then E has subexponential-size circuits with PP gates. That is consistent with the fact that an oracle proof of PH not in PP gives a relativized lower ...


10

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 form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq ...


10

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 of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the ...


9

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}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident. We can illustrate this by comparisons between ...


8

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 expect that to be true anyways). This also implies, of course, that $\mathsf{P} \neq \mathsf{BPP}$, so anything which implies $\mathsf{P} = \mathsf{BPP}$ ...


8

I'm not an expert, but perhaps some (not-so-natural?) examples can be directly derived using the technique of deterministically reducing BPP search problems to BPP decision problems, presented in: Oded Goldreich, In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232 In particular see Theorem 3.5: (reducing search to decision): For every ...


7

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 inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\...


7

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 chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma_2^p\subseteq DTIME[2^{n^{o(1)}}]$, ...


7

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 worst-case running time is $L_n(1/3, 2.77)$ unconditionally and $L_n(1/3, (64/9)^{1/3})$ under GRH. This is not for the "classic" number field sieve, but a ...


6

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. The difficult question is how to compute a deterministic isolating scheme more quickly than finding a perfect matching.


6

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 polylogarithmic running time (see the Handbook of Theoretical Computer Science Vol. A). So the question is whether every efficient randomised parallel algorihm can be ...


6

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 correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits. Indeed, by $\sigma$-...


6

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 $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) ...


6

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 ⊆ P / poly, then EXP^NP would be equal to EXP... We also know that if NEXP ⊆ P/poly, then NEXP = MA. Nevertheless, we do know that EXP^NP^NP is not in P/Poly.


5

There are several notions of randomness in computability theory (/the arithmetic hierarchy; lookup "Martin-Lof randomness", "Kurtz random", "Schnorr random", ...), but I think the ones that are analogous to $\mathsf{BPP}$ become trivial in the setting of the arithmetic hierarchy. The reason is essentially that a randomized Turing machine with bounded error ...


4

The proof of Theorem 4.1 states that: Let $S$ be the connected component of $G$, such that $s \in S$. By the arguments above, $S \times [N]$ is a connected component of $G_{\mathrm{reg}}$, and $G_{\mathrm{reg}}|_{S\times [N]}$ is non-bipartite. [...] By Lemma 3.2 and Lemma 3.3, we have that $\lambda(G_{\exp}|_{S\times[N]\times([D^{16}_{\mathbf{e}}])...


4

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 $n$ at $n$ different points in $\tilde{O}(n)$ time).


3

There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument. Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$ of size $k$. We will show that there is always {-1,0,1}-linear form $f$ such that $f(\alpha_{i})=0$ for all $i$ when $k\le c_{0}n/\log n$ and $c_{0}$ is small enough. For each $S\subseteq[n]$, let $f_{S}=\...


3

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 (FPE) might be helpful. Let me sketch a few different constructions of this sort. (By "computational notion of $k$-wise independence", I mean that no ...


Only top voted, non community-wiki answers of a minimum length are eligible