38

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


16

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


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


14

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

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


11

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


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


11

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


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

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

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


9

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


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

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


9

This isn't my area, so many apologies if I say something incorrect: 1) "What evidence do we have that $\mathsf{BPP}\subseteq \mathsf{REXP}$?" Isn't this unconditionally true? It should follow from $\mathsf{BPP}\subseteq \mathsf{EXP}$, and in fact by Sipser-Gács-Lautemann $\mathsf{BPP}\subseteq \Sigma^p_2\cap \Pi_2^p$. 2) "What consequences does $\mathsf{...


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

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


8

Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698 Related hardness results: Boson sampling: http://arxiv.org/abs/1011.3245 Commuting circuits: http://arxiv.org/abs/1005.1407 DQC1 model: http://arxiv.org/abs/1509.07276 Extended Clifford circuits: http://arxiv.org/abs/1305.6190


8

I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom ...


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

For concreteness, say that the pdf of the r.v. $X_i$ is $$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$ This is the Laplace distribution, or the double exponential distribution. Its variance is $\frac{2}{\lambda_i^2}$. The cdf is $$ \Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x} $$ for $x \geq 0$. The moment generating function of $X_i$ ...


7

Although there aren't any problems known to be $\mathsf{BPP}$-complete (and Sipser gave an oracle relative to which $\mathsf{BPP}$ doesn't have complete problems), one topic to look at here is pseudorandom generators. The existence of a good enough pseudorandom generator implies $\mathsf{BPP} = \mathsf{P}$. This isn't $\mathsf{BPP}$-complete, but it does ...


7

It doesn't sound hopeful in general. For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high probability the graph is 0-regular or 1-regular, so $P$ holds with high probability. Also $P$ is preserved by removing edges. But it is certainly not the case that $...


7

Intuitively, the situation is you'd like some deterministic extractor $E: \{0,1\}^n \rightarrow \{0,1\}$ that can take in $n$ bits sampled from a weak source and output one bit with probability close to $1/2$, say it outputs 0 with probability $1/2 \pm \epsilon$ and 1 with $1/2\pm\epsilon$. Here's a weak argument that at the very least, such extractors $E$ ...


7

It's not uncommon for Wikipedia to say dubious things. Don't trust it as a primary reference. Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability. When you find something in Wikipedia you don't understand, my advice is ...


6

The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.


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