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.
164
questions
49
votes
11
answers
3k
views
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a ...
44
votes
7
answers
6k
views
Truly random number generator: Turing computable?
I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable. I don't know how to phrase this precisely.
This StackExchange question on "efficient ...
39
votes
9
answers
27k
views
What is the difference between non-determinism and randomness?
I recently heard this -
"A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
37
votes
1
answer
1k
views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.
Conjecture. Let $\mu(k)$ ...
36
votes
1
answer
3k
views
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \...
32
votes
4
answers
4k
views
Can a probabilistic Turing machine solve the halting problem?
A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem?
That is, can a ...
31
votes
2
answers
1k
views
Hierarchy for BPP vs derandomization
In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?
A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ ...
25
votes
1
answer
777
views
Random self-avoiding lattice cycle within a given bounding box
In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all ...
23
votes
2
answers
2k
views
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
22
votes
2
answers
2k
views
Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?
If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\...
22
votes
1
answer
487
views
Random functions of low degree as a real polynomial
Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?
EDIT: Nisan and Szegedy have shown that a ...
22
votes
1
answer
342
views
Belief propagation for approximate real 3LIN?
In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-...
21
votes
1
answer
335
views
A comparison of extractors in terms of tradeoffs between time, randomness and space ?
Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
20
votes
4
answers
706
views
Is there current research into the implemention of Randomness Extractors?
Has there been research into implementing randomness extractor constructions?
It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
20
votes
3
answers
1k
views
Problems that are NP-complete under randomized or P/poly reductions.
In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which ...
20
votes
2
answers
644
views
Bounded depth probability distributions
Two related questions about bounded depth computing:
1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
20
votes
0
answers
812
views
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up ...
17
votes
3
answers
725
views
Randomize or Not?
This question is inspired by the Georgia Tech Algorithms and Randomness Center's t-shirt, which asks "Randomize or not?!"
There are many examples where randomizing helps, especially when operating in ...
16
votes
1
answer
1k
views
Number of Hamiltonian cycles on random graphs
We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
15
votes
1
answer
898
views
Random monotone function
In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...
15
votes
1
answer
468
views
Natural theorems proven only "to high probability"?
There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.
Question: Are there any natural ...
14
votes
2
answers
482
views
What's the bias of random polynomials with low degree over GF(2)?
I have a question concerning low-degree polynomials and probability:
What is the (assyptotic behavior of the) probability that a
random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
14
votes
1
answer
338
views
How much independence is required for separate chaining?
If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
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[...
13
votes
2
answers
377
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, ...
13
votes
2
answers
3k
views
Sum of Independent Exponential Random Variables
Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - e^{-x/\...
13
votes
1
answer
286
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$....
13
votes
0
answers
179
views
Generating a random graph with constraints on spectrum
Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
12
votes
2
answers
2k
views
What is the precise definition of Random K-SAT?
There are 4 different constraints we can have when defining Random K-SAT. 1)Total number of literals in a given clauses is exactly K or AT most K
2)A given literal can be used with or without ...
12
votes
1
answer
1k
views
Is there a problem in ZPP not yet in P?
Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P ...
12
votes
1
answer
521
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 + ...
12
votes
1
answer
413
views
Measuring the randomness of CNF formulas
It's widely known that CNF formulas can be roughly partitioned in 2 broad classes: random vs. structured. Structured CNF formulas, in opposition to random CNF formulas, exhibit some sort of order, ...
12
votes
0
answers
278
views
Conditional density of primes
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.
My question is
about the density of primes when we choose random numbers from a ...
12
votes
0
answers
374
views
Oracle relative to which MA does not have a complete problem?
Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
11
votes
1
answer
726
views
Time complexity analysis for Reingold's UST-CONN algorithm
What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
11
votes
3
answers
463
views
Randomized algorithms using a stack
I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural ...
11
votes
1
answer
422
views
Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation?
The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
11
votes
1
answer
314
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 ...
10
votes
3
answers
646
views
What is the fastest known simulation of BPP using Las Vegas algorithms?
$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.
$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
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 ...
10
votes
1
answer
267
views
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
10
votes
0
answers
200
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 ...
9
votes
1
answer
464
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 ...
9
votes
1
answer
202
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 ...
9
votes
2
answers
351
views
Almost universal string hashing in $Z_{2^n}$ and sublinear space
Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:
For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \...
9
votes
1
answer
322
views
The power of randomized logspace with two-way access to the random tape
Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the ...
9
votes
0
answers
507
views
Statistical relationship between diameter and density in strongly connected random digraphs
I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
8
votes
8
answers
4k
views
Best way to determine if a list of bytes are random?
Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called Data Entropy.
I recently read this article: http://faculty.rhodes.edu/wetzel/...
8
votes
2
answers
607
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}$ ...
8
votes
2
answers
1k
views
How to analyze a randomized recursive algorithm?
Consider the following algorithm, where $c$ is a fixed constant.
...