Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
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?
arnab's user avatar
  • 7,000
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 ...
Joseph O'Rourke's user avatar
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 ...
Joey Adams's user avatar
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}$ ...
Sasho Nikolov's user avatar
22 votes
1 answer
497 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 ...
Igor Shinkar's user avatar
  • 1,927
21 votes
1 answer
336 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 ?
Suresh Venkat's user avatar
15 votes
1 answer
901 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 ...
Kaveh's user avatar
  • 21.7k
13 votes
0 answers
180 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 ...
Artem Kaznatcheev's user avatar
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 ...
Kaveh's user avatar
  • 21.7k
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 ...
domotorp's user avatar
  • 14k
12 votes
0 answers
376 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 ...
Dai Le's user avatar
  • 3,664
11 votes
1 answer
730 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 ?
user avatar
10 votes
3 answers
647 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 ...
echuly's user avatar
  • 549
9 votes
1 answer
480 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 ...
user avatar
7 votes
2 answers
804 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 ...
Turbo's user avatar
  • 12.9k
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 ...
tsudot's user avatar
  • 181
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 ...
Santiago's user avatar
4 votes
1 answer
814 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 ...
Simd's user avatar
  • 3,902
2 votes
1 answer
234 views

Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we ...
epsfooling's user avatar
2 votes
1 answer
210 views

Motivation for randomness extractors

I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must ...
sam10269's user avatar