# 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.

154 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
226 views

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)\...
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$ ...
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 ...
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 ...
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?
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 ...
74 views

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 ...
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 ...
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 ...
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)$ ...
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 ...
1k views

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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
### 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 \$\...