# Questions tagged [randomness]

Randomness is a key component of probabilistic algorithms, many combinatorial aarguments, the analysis of hashing functions, and in cryptography, among other applications.

156 questions
Filter by
Sorted by
Tagged with
117 views

### BPP version of a problem related to #P completeness

Given a $CIRCUITSAT$ instance $\varphi(n)$ in $n$ variables and a fixed $k>1$ the problem of deciding if the number of satisfying witnesses is $2^n\big(1-\frac1k\big)$ or $\frac{2^n}k$ is $PP$ ...
48 views

### Concentration bounds for hypergeometric distribution

I asked a similar question a while back. I have reformulated the question. My original intention was to ask this question. Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are ...
44 views

### Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

We have a sorted list of $n$ numbers and we shall create a BST for these numbers. We create a random sequence of zeroes and ones of length $n$. We shall make use of this random binary sequence to form ...
35 views

### Random variates generation in discrete-event simulation models

In discrete-event simulation, most university textbooks (e.g., Law & Kelton, Banks etc.) state that for generating variates for each random variable (e.g., interarrival time, service time etc.) in ...
144 views

### Provable BPP Hierarchy

No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition: A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
122 views

### Converting a Bernoulli to a Gaussian

It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a "...
150 views

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

All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it. So can we formalize this as follows? Suppose I can only sample from my distribution,...
131 views

### Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
162 views

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

Wikipedia article mentioned : Hypercomputation The third paragraph starts off with: Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
281 views

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

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, ...
60 views

### Randomized Reduction for Maximization Problem

I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
221 views

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

From $P=RP$ extrapolation we might think $EXP=REXP$. What evidence do we have $BPP\subseteq REXP$? What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
106 views

### BPP fragment of a PSPACE complete problem

Consider a PSPACE-complete problem (e.g., TQBF). Is there a sub-problem in BPP, that is not known to be in P? Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e....
79 views

### Expected value of a random experiment in a graph

I need to find the expected value of R in the random experiment below. $$R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]$$ $\mathcal{H}$ is a partition on ...
460 views

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

Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are Independent runs + ...
124 views

289 views

### UnambiguousSAT reductions

Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other. Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but ...
405 views

### Connectivity of a random regular graph of degree $d$

An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? ...
442 views

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

Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...