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
10
votes
1answer
254 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 ...
20
votes
2answers
635 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
226 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
285 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
143 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 in})...
16
votes
1answer
971 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)\...
7
votes
0answers
191 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$ ...
9
votes
1answer
266 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 ...
13
votes
2answers
404 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 ...
21
votes
2answers
1k 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?
6
votes
1answer
407 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
74 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 $\...
3
votes
2answers
2k 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 ...
10
votes
1answer
407 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
121 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 ...
9
votes
0answers
489 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
950 views

How to analyze a randomized recursive algorithm?

Consider the following algorithm, where $c$ is a fixed constant. ...
0
votes
1answer
262 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 ...
6
votes
3answers
1k 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 ...
22
votes
1answer
339 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-...
2
votes
1answer
236 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 ...
30
votes
2answers
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}$ ...
6
votes
1answer
341 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
231 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
569 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. $f(q(),...
25
votes
1answer
762 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 ...
12
votes
0answers
270 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 ...
48
votes
11answers
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 ...
37
votes
1answer
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)$ ...
8
votes
1answer
467 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 ...
0
votes
2answers
1k 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 ...
20
votes
3answers
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 ...
12
votes
1answer
386 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, ...
13
votes
2answers
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 ...
5
votes
0answers
309 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 ...
20
votes
4answers
660 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 ...
7
votes
0answers
557 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
240 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, ...
4
votes
3answers
1k 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 ...
13
votes
0answers
361 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 ...
4
votes
1answer
255 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 ...
20
votes
0answers
752 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 ...
30
votes
4answers
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 ...
15
votes
1answer
823 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 ...
17
votes
3answers
713 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 ...
6
votes
1answer
654 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 ...
11
votes
3answers
453 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 ...
42
votes
7answers
5k 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 ...
11
votes
1answer
666 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 ?
22
votes
2answers
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 $\...