Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
50 views

Does randomness help depth?

Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$? Is there any evidence for ...
Turbo's user avatar
  • 13k
0 votes
1 answer
140 views

Parity of the sum of pseudorandom bits over a non-sparse set of inputs

Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse,...
Tejas's user avatar
  • 369
11 votes
1 answer
373 views

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

I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i). The proof starts by saying Clearly, $...
deltaepsilonnn's user avatar
0 votes
0 answers
34 views

What’s the difference between P-computable distributions and P-samplable distributions?

$\newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}}$ I have two questions and the first one is presented in the title. The second one is about the ...
Heda Chen's user avatar
  • 181
4 votes
1 answer
159 views

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

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
rus9384's user avatar
  • 355
3 votes
2 answers
223 views

Do pseudo-random number generator test batteries have any theoretical grounding?

There are a lot of PRNG test batteries, like DieHarder. They do check that some statistical tests expected for random sequence are indeed present. But is there any theoretical motivation, why this ...
uhbif19's user avatar
  • 315
0 votes
0 answers
73 views

Are there any examples of problems in ZPP not yet in P? [duplicate]

Is there a problem of which we can prove that it is in ZPP but we don’t yet know whether it’s in P or not?
blademan9999's user avatar
3 votes
0 answers
136 views

Inverse of leftover hash lemma

Leftover hash lemma: Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
delete000's user avatar
  • 828
2 votes
1 answer
419 views

Chernoff bound for weighted sums of Bernoulli random variables

I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest. Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a ...
Xinyu Mao's user avatar
13 votes
3 answers
2k 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[...
Arthur B's user avatar
  • 429
5 votes
1 answer
299 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 $...
Punga's user avatar
  • 153
1 vote
0 answers
251 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$ (...
Annonymous's user avatar
0 votes
1 answer
136 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 ...
Turbo's user avatar
  • 13k
0 votes
0 answers
122 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 ...
Vk1's user avatar
  • 137
1 vote
0 answers
116 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 ...
E-O's user avatar
  • 21
11 votes
0 answers
302 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 ...
domotorp's user avatar
  • 14k
3 votes
1 answer
235 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 "...
Clement C.'s user avatar
  • 4,471
4 votes
1 answer
201 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,...
Karagounis Z's user avatar
0 votes
1 answer
233 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 ...
Giorgio Camerani's user avatar
1 vote
1 answer
321 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 ...
Novicegrammer's user avatar
13 votes
2 answers
386 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, ...
Morgan Shirley's user avatar
0 votes
0 answers
76 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 ...
tc1729's user avatar
  • 101
-1 votes
1 answer
246 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?
Turbo's user avatar
  • 13k
4 votes
0 answers
152 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....
Shaull's user avatar
  • 5,656
0 votes
0 answers
87 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 ...
Morten Movik's user avatar
12 votes
1 answer
529 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 + ...
Clement C.'s user avatar
  • 4,471
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}...
Mark Schultz-Wu's user avatar
2 votes
1 answer
512 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 ...
Hope's user avatar
  • 29
2 votes
1 answer
98 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 ...
Clement C.'s user avatar
  • 4,471
3 votes
1 answer
268 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 ...
Clement C.'s user avatar
  • 4,471
4 votes
1 answer
193 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. ...
satya's user avatar
  • 141
5 votes
1 answer
263 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 ...
Clement C.'s user avatar
  • 4,471
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 ...
Timon Knigge's user avatar
5 votes
1 answer
170 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 ...
Elle Najt's user avatar
  • 1,469
5 votes
1 answer
480 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 ...
Elle Najt's user avatar
  • 1,469
4 votes
0 answers
162 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.
user124297's user avatar
1 vote
0 answers
142 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 ...
s3683168's user avatar
2 votes
1 answer
213 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 ...
sam10269's user avatar
-1 votes
1 answer
168 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 ...
user124297's user avatar
1 vote
2 answers
368 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 ...
Christopher King's user avatar
9 votes
1 answer
205 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 ...
Samuel Schlesinger's user avatar
1 vote
0 answers
143 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 ...
tranisstor's user avatar
1 vote
0 answers
212 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 ...
user1767774's user avatar
4 votes
0 answers
189 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 ...
Turbo's user avatar
  • 13k
2 votes
1 answer
478 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 ...
polar_bear_cheese's user avatar
7 votes
1 answer
472 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) := ...
StefanH's user avatar
  • 2,077
4 votes
1 answer
342 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 ...
Turbo's user avatar
  • 13k
7 votes
1 answer
587 views

Connectivity of a random regular graph of degree $d$

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be ...
Vivek Bagaria's user avatar
10 votes
1 answer
459 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 ...
Thomas Klimpel's user avatar
2 votes
1 answer
192 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\...
Vivek Bagaria's user avatar