The pseudorandom-generators tag has no wiki summary.
1
vote
0answers
25 views
What upper bound can we get under 3-wise independent?(comparable edition)
Here is the original question: What bound can we get using kth moment inequality under 3-wise independent? .Yury has given a 3-wise independent example that shows the upper bound is no better than ...
11
votes
2answers
328 views
On fooling $AC^0$
I have a few questions regarding fooling constant depth circuits.
It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the ...
8
votes
1answer
265 views
How hard is it to learn a linear modular function?
Let $k$ be a fixed number.
Consider the following task $Q$:
We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where ...
15
votes
3answers
315 views
What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?
I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : ...
9
votes
1answer
166 views
Generating graphs of girth $g$ such that the minimum cycles form a double edge cover
Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and ...
16
votes
2answers
706 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 ...
2
votes
1answer
200 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 ...
2
votes
0answers
235 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 ...
4
votes
1answer
185 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 ...
0
votes
1answer
202 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 ...
19
votes
3answers
545 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 ...
8
votes
2answers
305 views
Are linear feedback shift registers being generally discouraged by cryptologists?
Katz and Lindell mention in their book that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ...
20
votes
6answers
745 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 ...
1
vote
0answers
118 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 ...
1
vote
3answers
385 views
Simple question about pseudorandom generator
I am stuck on the following question related to pseudorandom generator and any help would be appreciated.
Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define ...
19
votes
2answers
471 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 ...
11
votes
3answers
350 views
Streaming derandomization
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
