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
39
votes
9answers
23k 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 ...
8
votes
8answers
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/...
7
votes
4answers
2k 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 ...
21
votes
1answer
319 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 ?

1 2 3
4