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.
4
votes
1answer
106 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. ...
4
votes
1answer
138 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 ...
1
vote
1answer
56 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 ...
5
votes
1answer
142 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 ...
5
votes
1answer
217 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 ...
4
votes
0answers
136 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.
1
vote
0answers
101 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 ...
3
votes
1answer
146 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 ...
-1
votes
1answer
145 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 ...
1
vote
2answers
183 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 ...
9
votes
1answer
145 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
votes
0answers
30 views
What ways are there to measure the smoothness or structure of sampled data?
Specifically I have vector data which may be drawn from unknown distributions. It may be highly structured similar to GPS vehicle locations or part positions in a construction plan. It probably ...
1
vote
0answers
123 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 ...
1
vote
0answers
125 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 ...
4
votes
0answers
158 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 ...
3
votes
1answer
210 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 ...
7
votes
1answer
311 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) := ...
4
votes
1answer
236 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 ...
6
votes
1answer
299 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? ...
-2
votes
0answers
81 views
Could we use transcendental numbers as an RNG?
Numbers like pi and other transcendentals seem to have some nice properties, viz, we can't find patterns in them. Seems to me this could make them a nice candidate for RNGs, especially given that we ...
11
votes
1answer
385 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 ...
2
votes
1answer
156 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\...
3
votes
1answer
164 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. ...
4
votes
0answers
58 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$.
...
1
vote
1answer
324 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 ...
1
vote
0answers
140 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 ...
2
votes
1answer
376 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\...
7
votes
1answer
59 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) \...
6
votes
1answer
197 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 ...
3
votes
1answer
471 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 ...
6
votes
1answer
205 views
Evidence that there is some problem in BQP distinct from BPP?
Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be ...
6
votes
1answer
160 views
Generating uniform integers in a range from a random generator with another range
Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to ...
-2
votes
1answer
327 views
What is the status of intermediate problems if P is not NP in worst way imaginable?
Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...
12
votes
1answer
224 views
Randomized Polynomial Hierarchy?
I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?
It seems, we could still build a hierarchy, the same ...
5
votes
0answers
130 views
Random Sampling Threshold to Get a Connected Induced Subgraph
Working on network design this summer I have come across certain applications that have inspired me to ask the following question:
Given an undirected connected graph $G=(V,E)$ what is the minimum ...
2
votes
1answer
113 views
Finding a random regular graph with degree d
I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.
For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
3
votes
0answers
104 views
How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?
Let $G=(V,E)$ be an undirected, random $r$-regular graph.
Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$.
I'm looking for the distribution of the number of ...
6
votes
2answers
422 views
Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?
DISCLAIMERI do apologize in advance if this question turns out to be
silly, for some trivial reason that I may be overlooking in this
moment.
Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ ...
12
votes
1answer
222 views
When does randomization stops helping within PSPACE
It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.
It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$....
5
votes
1answer
493 views
Example of pairwise independent random process with expected max load $\sqrt{n}$
This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
5
votes
0answers
145 views
Satisfiability threshold and partially random formulas
My understanding is that if we have a totally random k-SAT formula, for a ratio $m < \alpha n$ far enough below the satisfiability threshold, we can solve for satisfiability in polynomial time (...
5
votes
1answer
225 views
Deterministic Randomness Extractors
I have read in several papers it is well known that deterministically extracting even one bit from a weak source is impossible. Could someone explain why?
5
votes
0answers
151 views
Reconstruction of sparse vectors from random matrices
In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.
Lemma: Let $1 \...
1
vote
0answers
80 views
Eigenvalues of Random Regular Bipartite Graphs
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
2
votes
1answer
210 views
Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution
One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we ...
4
votes
1answer
146 views
How to Quantify Entropy in a Data Set
I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
4
votes
0answers
326 views
The largest connected component of a random subgraph
Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
6
votes
0answers
175 views
Bias of a random boolean low degree polynomial
What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree?
More specifically, is it true that if we take a uniformly ...
5
votes
1answer
170 views
Number of points on the interior of the convex hull of a random subset
This question is in regards to the following problem:
Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally ...
0
votes
1answer
204 views
Proving properties of Random Graphs
I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas.
Consider the random graph model $G_{n,p}$ where its ...
