The randomness tag has no wiki summary.
3
votes
2answers
117 views
Sort with random deviations
I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a ...
6
votes
2answers
124 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 ...
12
votes
0answers
175 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 ...
8
votes
3answers
357 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 ...
5
votes
0answers
79 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 \: : \: ...
6
votes
0answers
98 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 ...
-1
votes
2answers
291 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 ...
9
votes
0answers
110 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 ...
4
votes
1answer
199 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( ...
22
votes
1answer
406 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^ ...
8
votes
1answer
184 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 ...
17
votes
2answers
492 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 ...
3
votes
1answer
176 views
Coupon collector - the effect of randomization
Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x ...
3
votes
1answer
181 views
Are randomly generated infinite patterns computable?
Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the ...
4
votes
0answers
80 views
Strong extractors with reusable seeds
I have convinced myself of the following:
For every $(k,\epsilon^2\hspace{.005 in})$-strong extractor Ext, for every distribution $X$,
if $\;\; k\leq$ $\:H_{\infty}$$(\hspace{.01 in}X\hspace{.015 ...
14
votes
1answer
277 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 & ...
6
votes
0answers
94 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$ ...
6
votes
0answers
99 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 ...
12
votes
2answers
205 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 ...
16
votes
2answers
516 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?
5
votes
1answer
167 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 ...
3
votes
0answers
66 views
Are there any “two-sided” strong blenders?
My question is related to explicit extractors and strong blenders. We can define explicit strong blender in a straight forward way.
I want to know if there are any known explicit strong blenders ...
2
votes
2answers
474 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 ...
8
votes
1answer
335 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 ...
5
votes
1answer
113 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 ...
8
votes
0answers
183 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
2answers
575 views
How to analyze a randomized recursive algorithm?
Consider the following algorithm, where $c$ is a fixed constant.
...
0
votes
1answer
199 views
Non-computable=>normal?
If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite ...
4
votes
3answers
315 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 ...
20
votes
1answer
286 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 ...
2
votes
1answer
190 views
Simulating nondeterministic space-bounded computation using randomness
Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer ...
26
votes
2answers
751 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}$ ...
6
votes
1answer
223 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 ...
5
votes
1answer
200 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 ...
2
votes
4answers
390 views
Algorithmic distinctions between random and pseudorandom.
Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:
$f(r(),r()) = 1$ almost always.
...
24
votes
1answer
652 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 ...
11
votes
0answers
227 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 ...
35
votes
11answers
2k 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 ...
30
votes
0answers
747 views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently Gil Kalai and Dick Lipton both wrote a nice article on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and Riemann Hypothesis.
Conjecture. Let $\mu(k)$ be ...
8
votes
1answer
308 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 ...
-1
votes
1answer
365 views
Password checking algorithm
Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function.
Could it be used ...
16
votes
3answers
530 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 ...
10
votes
1answer
303 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, ...
10
votes
2answers
1k 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 ...
5
votes
0answers
287 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 ...
16
votes
4answers
392 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 ...
0
votes
0answers
380 views
Rabin karp string searching algorithm analysis [closed]
My prof said Rabin-Karp analysis in Introduction to algorithms by Cormen, Leiserson, Rivest, and Stein is wrong. Can someone point me to the correct analysis.
Thanks
6
votes
0answers
308 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 ...
3
votes
0answers
183 views
Is there any research on the notion of weak isolation?
(First of all, sorry for the long article which makes you want to skip through, but since the background and motivations are important to this question or it would be nonsense to the main problem, ...
1
vote
3answers
538 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 ...
