# Questions tagged [pseudorandom-generators]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
3answers
745 views

### From Extractors to Pseudorandom Generators?

Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Is there a ...
6answers
1k views

### Parallel pseudorandom number generators

This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it. Put simply, I have a Monte Carlo ...
2answers
499 views

### Explicit balanced matrix

Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones? Or probably it is ...
2answers
884 views

### Are theoretically sound pseudorandom generators used in practice?

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
3answers
380 views

1answer
220 views

### Pseudorandom generators indistinguishable by uniform deterministic adversaries

I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries. (For example, a monograph Pseudorandomness by Vadhan (here's its draft ...
1answer
164 views

### Generating uniform integers in a range from a random generator with another range

Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to ...
1answer
384 views

### What is full-entropy bit-strings?

I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term full-entropy bit-strings used in the third paragraph.
1answer
231 views

### Pseudo-Random Function families whose instances have full domain

The GGM construction gives (PRF) pseudo-random function families whose instance's input's are binary strings of a single length. I've convinced myself that one could get a PRF family whose instances ...
0answers
139 views

### More powerful generator than Nisan-Wigderson one

Nisan-Wigderson generator can be computed in $\log^{O(1)} n$ space and fools all constant-depth circuits of size poly($n$). I mean Theorem 5 here. I want another generator, that can be computed in ...
0answers
91 views

### Sampling Functions Efficiently vs Pseudorandom Generators

Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
0answers
102 views

### Looking for an exposition of the proof of the LMN theorem

Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem? The exposition of that in Ryan O'Donnel's book seems to use terminology and notation ...
0answers
78 views

### Inefficient pseudorandom distribution using a few random bits

In these slides, it is mentioned that for a class of functions $\mathcal{C}$, a pseudorandom generator is a distribution $D$ such that $D$ fools $\mathcal{C}$. $D$ is efficiently samplable. $D$ is ...
1answer
191 views

### Random flows through fixed network

A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the ...
1answer
1k views

### How to find the exact period of Blum-Blum-Shub random number generator?

I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product ...
0answers
177 views

### Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
1answer
67 views

### Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the ...
1answer
217 views

### Pseudorandom increasing sequence

I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It ...
0answers
114 views

### What upper bound can we get under 3-wise independence? (comparable edition)

Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than ...
3answers
674 views

0answers
169 views

### A question about combinatorial design in Nisan-Wigderson Generator

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that: $\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$. $\forall i \neq j \in [m]$, \$|S_i \cap S_j| \...
0answers
133 views

### Structured Graph Generation

I hope you can help. I am looking for the best way to generate random bipartite graphs with localised structure within one of the node types. Such that type A visits a local group of type B with a ...
1answer
247 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 ...