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

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


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

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


6

$ \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} $ This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+...


6

The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as in the common definition), then you need to expend bits on delimiting encodings. Self-terminating encodings have other advantages, and even though real ...


6

There is no such problem. If it's hard to sample, it's hard to integrate. Here is a sketch of the reason why. Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$. If you can integrate over the set of all solutions, here is an algorithm to sample from all solutions: Count the number of solutions; call it $N_0$. (As you say, this can be done ...


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