Skip to main content
15 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 ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Dylan McKay's user avatar
12 votes
Accepted

Expected number of random comparisons needed to sort a list

This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes ...
Neal Young's user avatar
  • 10.8k
10 votes
Accepted

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

For notational convenience define r.v.s $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$. ...
Neal Young's user avatar
  • 10.8k
9 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 ...
Ryan Williams's 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 $\...
Jason Gaitonde's user avatar
9 votes

Expected number of random comparisons needed to sort a list

I believe this takes $\Theta(n^2)$ oracle calls without replacement, and $\Theta(n^2\log n)$ oracle calls with replacement. Lower bound: Assume my list has a single pair $x[i], x[i+1]$ out of order. ...
SamM's user avatar
  • 1,685
7 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 ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
D.W.'s user avatar
  • 12.2k
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 ...
D.W.'s user avatar
  • 12.2k
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).
Alex Grilo's 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 ...
Kunal's user avatar
  • 76
6 votes

Expected number of random comparisons needed to sort a list

Not a complete answer, but here's a start. Consider the index $p_{k} \in \{1,\dots n \}$ to represent the $k$th object in the series, with respect to order. We have: $$x[p_{k}] < x[p_{j}] \...
user3257842's user avatar
6 votes

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It would be a very interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility). I'm ...
Eric Allender's user avatar
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 ...
Yuval Peres's 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 ...
D.W.'s user avatar
  • 12.2k
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)$, ...
Joshua Grochow's user avatar
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
domotorp's user avatar
  • 14k
3 votes
Accepted

Deterministic error reduction, state-of-the-art?

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions. ...
guest's user avatar
  • 96
3 votes
Accepted

Distributions which are intractable to sample from?

I'll expand my comment to an answer. Many combinatorial structures in graphs are actually NP-hard to sample from. The earliest example I can think of is JVV86 (Thm 5.1), which shows that there is no ...
Heng Guo's user avatar
  • 375
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 ...
kodlu's user avatar
  • 2,070
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}$....
Thomas Ahle's user avatar
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 ...
William Hoza's user avatar
  • 1,743
3 votes

Password checking algorithm

As much as you're being downvoted and attacked, your idea is absolutely right, correct, and valid. You've nearly reinvented bcrypt. Let's say we have encryption algorithm (doesn't matter which one): ...
Ian Boyd's user avatar
  • 131
3 votes
Accepted

Weighted balls and bins

Suppose you have $n$ balls. Take a random ball from each non-empty bin. Your expected weight is approximately $(1-1/e)T$. This holds because the probability that a bin is empty is $(1-1/n)^n \approx 1/...
Peter Shor 's user avatar
2 votes

Is true randomness and the physical Church-Turing thesis incompatible?

The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random ...
Thomas Klimpel's user avatar
2 votes
Accepted

Robustness to non-uniform randomness vs. one-sidedness

Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins. Let $D$ be a decider that is not one-sided. For $x \in \mathcal{Y}$, let $\...
D.W.'s user avatar
  • 12.2k
2 votes
Accepted

Optimal bounds for $k$-wise non-uniform random bits

$$s = \Theta( k \cdot ( t + \log n ) )$$ As the question mentions, there is an upper bound of $s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$ bits for the seed length. Specifically, sample a random ...
Thomas's user avatar
  • 2,803

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