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.
165
questions
8
votes
2
answers
1k
views
How to analyze a randomized recursive algorithm?
Consider the following algorithm, where $c$ is a fixed constant.
...
- 3,440
8
votes
1
answer
587
views
Complexity of percolation
In the context of bond percolation on $\mathbb{Z}^d$ where $d$ is a positive integer, consider the problem of computing a $2^{-k}$-approximation of the critical percolation $p_c$ given a lattice ...
- 113
8
votes
0
answers
584
views
Extracting randomness from Santha-Vazirani sources using a seed of constant length
This question is actually an exercise problem from Salil Vadhan's draft survey "Pseudorandomness" marked with a star (*) (see Chapter 6, Problem 6.6). I do not know other references.
We say a random ...
- 651
7
votes
4
answers
3k
views
What are the most effective algorithms to find random number?
I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set ...
- 181
7
votes
1
answer
561
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 ...
- 791
7
votes
2
answers
790
views
Proof Strategies on P versus BPP
Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are ...
- 12.9k
7
votes
1
answer
301
views
Is an infinite incomputable sequence random wrt a computable measure?
Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in ...
- 93
7
votes
1
answer
317
views
Running time of randomized algorithms
This is a very basic doubt, something I've always swept under the carpet.
The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized ...
user1694
7
votes
1
answer
466
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) := ...
- 2,077
7
votes
3
answers
200
views
Independent Node Degree in Undirected Graphs
Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in ...
- 525
7
votes
1
answer
767
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 ...
- 9,269
7
votes
2
answers
128
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.2k
7
votes
0
answers
236
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 ...
- 1,927
7
votes
0
answers
281
views
Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme
I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
- 831
7
votes
0
answers
158
views
Size complexity of probabilistic two-way automata for a Boolean function
I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
- 171
7
votes
0
answers
196
views
Communication complexity of random functions with limited independence
Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ ...
- 1,338
6
votes
3
answers
2k
views
Computational complexity of random sampling
I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a ...
- 61
6
votes
1
answer
423
views
In a random perfect matching of a regular bipartite graph, are all edges equally probable?
Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the ...
- 575
6
votes
1
answer
313
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 ...
- 429
6
votes
1
answer
373
views
Error reduction with expanders and derandomization
In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a ...
6
votes
1
answer
762
views
Definition of a monotone machine.
There is a definition of a 'monotone machine' in Li & Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these ...
aurevoirlesenfants
6
votes
1
answer
257
views
correlation in an almost independent set of random variables
Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that ...
- 81
6
votes
0
answers
77
views
Fast convergence of a contagion process in special graphs
The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira):
Define an indicator variable $...
- 531
6
votes
0
answers
233
views
Physical Proof for P versus BPP
Lipton asks for a physical proof of $P\neq NP$.
Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness?
...
- 12.9k
6
votes
0
answers
185
views
Squares of random binary matrices
Are there results/techniques pertaining to the analysis of squares of random matrices ?
More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with ...
- 666
5
votes
1
answer
268
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?
- 53
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 ...
- 1,439
5
votes
1
answer
125
views
Honest Majority unconditional coinflipping without private channels
All communication is assumed to be by the parties
taking turns making authenticated broadcasts.
Is there a way for $n$ parties, each with access to ideal local randomness, to jointly
choose a ...
user6973
5
votes
1
answer
252
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,461
5
votes
1
answer
242
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 ...
- 191
5
votes
1
answer
236
views
Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?
I have the following problem:
Given a set of path existence/absence constraints C (not necessarily for all pairs of vertices) and a (fixed) set of vertices V, generate a random DAG, s.t.
it is ...
- 674
5
votes
1
answer
465
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,439
5
votes
1
answer
272
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 ...
- 235
5
votes
1
answer
298
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
5
votes
0
answers
158
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 ...
5
votes
0
answers
158
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 (...
- 2,100
5
votes
0
answers
164
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 \...
5
votes
0
answers
136
views
Largest size for randomness extractor
Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...
- 425
5
votes
0
answers
93
views
How short can reversible representations of the n-bit primes be?
For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an
efficiently computable (deterministic) function $\;\; f \: : \: \{0\hspace{....
user6973
5
votes
2
answers
3k
views
Is a turing machine with random number generator more powerful?
Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a ...
- 161
5
votes
0
answers
317
views
Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$
I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.
I'm now searching for an intuitive, or geometric, or visual proof of ...
- 281
4
votes
3
answers
2k
views
What is mathematical difference between "random" and "unique"?
Once in a while when a question like "how I get good random numbers" is asked the suggested approach is to just generate an UUID. UUID looks like a random number and it is designed in such way that ...
- 239
4
votes
3
answers
4k
views
Will quantum computing pave the way for native, true RNGs?
Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user ...
- 249
4
votes
1
answer
261
views
Ranking with errors
I am looking for references for the following problem, which I feel must have been studied before. I have n items and I want to rank them. I randomise once at the beginning of the
process and then ...
- 3,902
4
votes
1
answer
806
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 ...
- 3,902
4
votes
1
answer
516
views
What is full-entropy bit-strings?
I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term
full-entropy bit-strings
used in the third paragraph.
- 831
4
votes
1
answer
153
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 ...
- 355
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,...
- 607
4
votes
1
answer
203
views
Arithmetic Analogues of P versus BPP
In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there?
If there is no such analogy, why is randomness in the resource bounded case ...
- 12.9k
4
votes
1
answer
507
views
Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/...
- 171