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.
159
questions
9
votes
3
answers
705
views
Expected number of random comparisons needed to sort a list
Consider the task of sorting a list x of size n by repeatedly querying an oracle. The oracle draws, without replacement, a random pair of indices (i, j), with i != j, and returns (i, j) if x[i] < x[...
- 317
5
votes
1
answer
278
views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$
$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...
- 153
1
vote
0
answers
174
views
Converse form of Chernoff bound
Suppose $X_1,\ldots,X_n$ are i.i.d. random variables, all with mean $p$, and we have the statement that $\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$, can we use this to conclude anything about $p$ (...
- 251
0
votes
1
answer
125
views
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Modifying following TedP
We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
- 12.5k
0
votes
0
answers
74
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 ...
- 137
1
vote
0
answers
90
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 ...
- 21
10
votes
0
answers
167
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 ...
- 13.7k
3
votes
1
answer
155
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
"...
- 4,361
3
votes
1
answer
180
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,...
- 577
0
votes
1
answer
164
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 ...
- 6,625
1
vote
1
answer
219
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 ...
- 173
12
votes
2
answers
328
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, ...
- 123
0
votes
0
answers
69
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 ...
- 101
-1
votes
1
answer
233
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?
- 12.5k
4
votes
0
answers
129
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....
- 5,316
0
votes
0
answers
86
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 ...
12
votes
1
answer
495
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 + ...
- 4,361
2
votes
1
answer
125
views
Lower bound on the worst-case unbiased coin flips to sample a distribution?
Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}...
- 778
2
votes
1
answer
366
views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
- 29
2
votes
1
answer
97
views
Robustness to non-uniform randomness vs. one-sidedness
Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly ...
- 4,361
3
votes
1
answer
217
views
Optimal bounds for $k$-wise non-uniform random bits
Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.
What is the smallest sample space (or, equivalent, how many true independent random bits are ...
- 4,361
4
votes
1
answer
152
views
Strong seeded randomness extractors with low entropy loss
I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.
Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
- 141
4
votes
1
answer
204
views
Newman's lemma for distributional communication complexity
This may be obvious — sorry if it is.
Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
- 4,361
0
votes
1
answer
61
views
What forms of randomness are 'allowed' in FPRASs?
I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able ...
- 71
5
votes
1
answer
162
views
Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)
I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:
1) It is hard ...
- 1,429
5
votes
1
answer
367
views
Distributions which are intractable to sample from?
I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.
I'm not sure what the right notion of intractable is, though I know the notion ...
- 1,429
4
votes
0
answers
158
views
research problem for undergraduate majoring in Computer Science and Mathematics
I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.
- 141
1
vote
0
answers
134
views
Proof of Sipser-Lautmann Theorem
I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
- 21
2
votes
1
answer
184
views
Motivation for randomness extractors
I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must ...
- 23
-1
votes
1
answer
165
views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
- 141
1
vote
2
answers
309
views
Is true randomness and the physical Church-Turing thesis incompatible?
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
- 471
9
votes
1
answer
193
views
What is the probability that a random Boolean function has a trivial automorphism group?
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there ...
- 1,552
1
vote
0
answers
137
views
Cluster Assignment in the Stochastic Block Model
Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are ...
- 143
1
vote
0
answers
183
views
An alternative model of a probabilistic Turing machine [closed]
A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
- 111
4
votes
0
answers
184
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
- 12.5k
2
votes
1
answer
419
views
Weighted balls and bins
Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$. We throw the balls into the bins randomly, i.e., each ball lands into a random ...
- 239
6
votes
1
answer
407
views
Where does the "intuitive" understanding of Kolmogorov complexity fails
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.
So to give this more formal meaning, define
$$
K'(x) := ...
- 1,947
4
votes
1
answer
304
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 ...
- 12.5k
5
votes
1
answer
426
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? ...
- 771
10
votes
1
answer
451
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 ...
- 3,013
2
votes
1
answer
168
views
Probability of random variable $X$ less than $max(Y_i)$
For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.
Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\...
- 771
3
votes
1
answer
211
views
The average number of compressible strings in a random set of random strings
In the book Elements of Information Theory (p.446), it is stated:
...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. ...
- 133
4
votes
0
answers
65
views
Embedding of "large" graphs into random graph
Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$.
When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$.
...
- 243
2
votes
1
answer
486
views
How to generate Extended Finite State Machines Randomly with some properties?
This is related to my academic project
An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified):
$I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for ...
- 87
1
vote
0
answers
235
views
How does one sample uniformly at random from an uncountably infinite set?
I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible)
Does it help if the sample ...
- 644
2
votes
1
answer
561
views
Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?
May be this is trivial but I do not know the answer.
As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds.
As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\...
- 12.5k
7
votes
2
answers
126
views
Shoup-style hashing without one-wayness
Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \...
- 11.1k
0
votes
1
answer
64
views
Factoring random selfreducibility analogy from discrete logarithm
It is stated in https://en.wikipedia.org/wiki/Random_self-reducibility#Discrete_logarithm that if discrete log is easy for $\frac 1{poly(\log|G|)}$ of all inputs, then discrete log has a randomized ...
- 12.5k
6
votes
1
answer
251
views
Graph that maximizes minimum hitting time?
Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current ...
- 389
3
votes
1
answer
833
views
Real number $p$ such that a $p$-coin makes the undecidable decidable [closed]
This is an exercice from Arora & Barak, Chapter 7 :
Describe a real number $p$ such that given a random coin that comes up
"heads" with probability $p$, a Turing machine can decide an ...
- 312