# Tagged Questions

The tag has no usage guidance.

586 views

### Examples of successful derandomization from BPP to P

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)? The only example that comes ...
123 views

### How does one sample uniformly at random from an uncountably infinite set?

I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible) Does it help if the sample ...
139 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 ...
97 views

74 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 ...
251 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 ...
192 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 ...
182 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 ...
63 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 ...
62 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 ...
567 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 ...
173 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.
112 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 ...
420 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 ...
313 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 ...
361 views

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 : B^{l(... 1answer 201 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 ... 2answers 835 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 ... 1answer 215 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 ... 1answer 645 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 ... 1answer 226 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 ... 1answer 218 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 ... 3answers 624 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 ... 2answers 317 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 ... 6answers 926 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 ... 0answers 130 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 ... 3answers 576 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$G':\{0,1\}^{...
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 ...