The tag has no wiki summary.

learn more… | top users | synonyms

10
votes
2answers
123 views

Pseudorandom generator for finite automata

Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata? Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes ...
6
votes
1answer
141 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 ...
3
votes
1answer
171 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 ...
2
votes
1answer
55 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 ...
1
vote
1answer
47 views

nested pseudorandom generator

Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer ...
11
votes
1answer
447 views

Impagliazzo and Wigderson's famous P=BPP paper

I'm reading Impagliazzo and Wigderson's famous $\mathsf P=\mathsf{BPP}$ paper in 1997. Since I'm new to this field and the paper is a concise conference version, I have difficulty following their ...
3
votes
1answer
106 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.
2
votes
0answers
106 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 ...
11
votes
2answers
380 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 ...
7
votes
1answer
303 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 ...
16
votes
3answers
342 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
189 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 ...
17
votes
2answers
776 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
214 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
1answer
444 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
213 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
212 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 ...
20
votes
3answers
589 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
312 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
849 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
128 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
505 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
482 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
373 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 ...