16 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

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 ...
user avatar
  • 7,052
13 votes

Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

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 ...
user avatar
12 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

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 ...
user avatar
  • 5,983
11 votes

Random functions of low degree as a real polynomial

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 ...
user avatar
10 votes
Accepted

Connectivity of a random regular graph of degree $d$

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 ...
user avatar
  • 14.1k
9 votes
Accepted

When does randomization stops helping within PSPACE

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}$ ...
user avatar
9 votes
Accepted

Graph that maximizes minimum hitting time?

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 (...
user avatar
9 votes
Accepted

Does two-sided error have more capability than one-sided error?

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 $\...
user avatar
8 votes

Evidence that there is some problem in BQP distinct from BPP?

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....
user avatar
8 votes

n irrational number whose digits are pseudo-random: conceptual mismatch?

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 ...
user avatar
8 votes

Randomized Polynomial Hierarchy?

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 ...
user avatar
8 votes
Accepted

Example of pairwise independent random process with expected max load $\sqrt{n}$

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 ...
user avatar
8 votes
Accepted

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

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 ...
user avatar
7 votes
Accepted

Deterministic Randomness Extractors

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 ...
user avatar
  • 2,295
7 votes

Proving properties of Random Graphs

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 ...
user avatar
7 votes
Accepted

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

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 ...
user avatar
  • 10.4k
6 votes
Accepted

Where does the "intuitive" understanding of Kolmogorov complexity fails

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 ...
user avatar
  • 14.1k
6 votes
Accepted

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

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 ...
user avatar
  • 10.4k
6 votes

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

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).
user avatar
6 votes
Accepted

Converting a Bernoulli to a Gaussian

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 ...
user avatar
  • 76
5 votes

Generating $k$ random bits from a pdf with entropy $H(p) = k$

The relevance of Shannon entropy is to repeated sampling: Given $n$ independent samples from a source with binary Shannon Entropy $k$, you can extract $nk(1+o(1)$ i.i.d. uniform bits as $n$ tends to ...
user avatar
4 votes
Accepted

What is the probability that a random Boolean function has a trivial automorphism group?

Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, ...
user avatar
4 votes
Accepted

Motivation for randomness extractors

Here we have $d \ll m$, i.e., we start with a little bit of good randomness, and we end up with a lot. That's why it's called a "seed": you need something small to get you started, but you end up ...
user avatar
  • 10.4k
4 votes
Accepted

Newman's lemma for distributional communication complexity

There's nothing wrong in your proof, but you can do even better; by taking the average in $$ \mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon $$ you can conclude ...
user avatar
  • 13.5k
4 votes

How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time?

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up ...
user avatar
  • 10k
3 votes
Accepted

The average number of compressible strings in a random set of random strings

The answer is less than $2^{n-k}$ of the sequences of length $n$ have complexity less than $<n-k.$ Due to the uniformity assumption on these sequences we just count. Consider all short programs of ...
user avatar
  • 1,986
3 votes

Sum of Independent Exponential Random Variables

For the Laplace distribution, if you use the Bernoulli bound you can write $$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$$ where $\sigma^2=2\sum_i\lambda_i^{-2}$....
user avatar
3 votes
Accepted

How much independence is required for separate chaining?

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [...
user avatar
  • 11k
3 votes

The power of randomized logspace with two-way access to the random tape

Well, here are a couple of observations. There's a famous PRG by Nisan that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be ...
user avatar
  • 1,733

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