# Tag Info

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

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

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 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$ \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 meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.

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

6

If you are happy with impying $P=RP$ (which implies $P = ZPP$) but not $P = BPP$, then there is the Stoquastic PCP conjecture (or its classical version, a SetCSP PCP conjecture).

6

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively. Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ ...

5

There have been interesting developments on this problem, however Replacing $AC^0$ with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://...

5

I'd imagine that you'd have to go from first principles, by taking a TM that exhibits an arbitrary BPP algorithm and simulating it in P. This is how it is shown that $\mathsf{BPP} \in \Sigma_2 \cap \Pi_2$. In particular, you have to "derandomize" the space of random choices much like it is done for specific problems, where a small set of carefully chosen ...

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