We’re rewarding the question askers & reputations are being recalculated! Read more.
37

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize. But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, ...


21

Moved my comment here after Suresh's request. An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP. Reference: see ...


20

An arguably more natural problem - not designed specifically for the purpose of finding a problem that might be in $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$, and also not so closely related to a problem known to be in $\mathsf{coRP}$ - is furnished by Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \...


15

As was pointed out at the beginning of this discussion in the comments, there is not necessarily a single "right" definition for random $k$-SAT. That said, the two most common variants of random $k$-SAT are both fixed clause length (FCL) models, meaning that exactly $k$ literals appear in each clause. These variants both disallow repeated variables and ...


14

[Edited for clarity] The most widely used definition in the research literature is the one that requires exactly k distinct variables per clause, and no duplicate clauses. If you relax the distinct variables restriction, much of the existing research won't make sense to you because your results will not match their results. The well known sat/unsat phase ...


14

There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits. Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless ...


13

Actually, today's computers can generate truly random data on their own, and many in fact do. The random data is produced as a byproduct of the physics of the components, not as the product of a given algorithm, so it necessarily has to be implemented in hardware. But the hardware is readily available. The popular TPM chip, for example, typically has an ...


13

First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades....


13

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in ...


13

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first") ...


12

Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the probability of the outcome, even for polynomial-depth classical circuits. This, of course, does not tell you what resctrictions $\mathsf{QNC^0}$ circuits will ...


12

No. Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.


11

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs ...


11

Here's an algorithm that beats the trivial attempts. The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as a polynomial, then every Fourier coefficient of $f$, $\hat{f}(S)$ is an integer multiple of $2^{-d}$. Using Cauchy-Schwarz and Parseval one gets that there are ...


10

Yes, quantum computation allows the generation of truly random numbers, and the operations necessary are so simple companies like id Quantique are already selling quantum random number generators. It is even possible to generate random numbers in a way that proves to the person generating them that they are random (via a violation of Bell's inequality) but ...


10

Mucknik, Semenov and Uspensky showed that there are sequences which are not Martin-Löf random for any computable measure. They call all other sequences (which are Martin-Löf random for some computable measure) "natural sequences". Andrei A. Muchnik, Alexei Semenov, and Vladimir Uspensky. Mathematical metaphysics of randomness. Theoretical Computer ...


10

Here's how to do it. First, choose a random $k$ between 1 and $n$ to be the "crowded bin". Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$. Now, for $1 \leq i \leq n-1$, $$ \mbox{put ball } i \mbox{ into bin } \begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\ k + \pi(i) \mbox{ with probability }1 - \frac{...


10

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.


9

Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability. First consider the algorithm modified so that $k$ is chosen in $\{2,3,..,\min(c,n)\}$ instead of randomly in $\{1,2,...,\min(c,n)\}$. Lemma 1. For this modified algorithm, regardless of the random choices of the algorithm, the time is always $O(n\,m)$. ...


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


9

The questions touches on some very interesting issues regarding quantum computation (and randomness). BQP is the class of decision problems that can be solved efficiently (in polynomial time) but it is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability ...


9

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the ...


8

It depends on what assumptions you are willing to make. Under certain hardness assumptions, namely $E \not\subseteq SIZE(2^{\varepsilon n})$, you get that $P = BPP$. This in particular implies that $BPP = ZPP$, and therefore that every language $L \in BPP$ is accepted by a Las Vegas machine (see "P=BPP unless E has Subexponential Circuits: Derandomizing the ...


8

Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and $2^k$. With probability at least $\tfrac{1}{2}$, $0\leq r < n$ so use that as your answer; otherwise, try again. If you've not succeeded after $t$ attempts, reject your input. The probability of this happening is at most $2^{-t}$, which can be made as small ...


8

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior. Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (...


8

Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (Buhrman&Fortnow, pdf), so the only way the hierarchy didn’t collapse to (at most) the second level and didn’t exhaust $\mathrm{BPP}$ would be for the unlikely reason that $\mathrm{RP}$ oracles were significantly weaker than $\mathrm{promiseRP}$ ...


7

$E[m]$ equals $n(H_n-1)$. Here's a more complete proof sketch, following the argument suggested in my comment. We start by showing that each permutation of the first $k-1$ elements is equally likely. More precisely, let $X^*=(X_1,X_2,\ldots,X_K, \ldots)$ be an infinite random sequence where each $X_i$ is drawn independently and uniformly from $S$. Let ...


7

As Yuval said, Q1 is easy to answer using linearity of expectation (spoiler: $(n-1)!p^n$) . I don't know the exact answer to Q2, but it might be good enough if you know it's very low: for the range of $p$ where there is at least one cycle, it holds that $P[\text{there is more than one cycle} | \text{there is at least one cycle}]>1-1/n^{\log n}$ or so. In ...


7

The answer depends on your computational model. Sometimes people just assume you can generate a Gaussian as a unit operation. However, if all you can generate is, say, random bits, and you want an approximate Gaussian, the complexity depends on the approximation you want.


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