Questions tagged [pseudorandomness]
The pseudorandomness tag has no usage guidance.
55
questions
25
votes
1
answer
662
views
$RL=L$ Progress Since 2006
Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are ...
- 441
23
votes
3
answers
849
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 ...
- 10.9k
20
votes
2
answers
523
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 ...
- 1,559
17
votes
2
answers
937
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 ...
- 3,708
17
votes
1
answer
526
views
Fooling arbitrary symmetric functions
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
- 2,447
17
votes
0
answers
311
views
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
- 3,708
16
votes
3
answers
414
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 : B^{l(...
- 163
15
votes
3
answers
665
views
Surveys on pseudo-random number generator design?
I am interested in generation of pseudo-random numbers for cryptography. Besides Chapter 5 of Menezes/Oorschot/Vanstone; Chapter 8 of Stinson; and Chapter 3 of Goldreich, where else could I find more? ...
- 962
12
votes
2
answers
369
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 ...
- 638
12
votes
1
answer
491
views
Deterministic error reduction, state-of-the-art?
Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are
Independent runs + ...
- 4,341
10
votes
1
answer
450
views
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...
- 3,013
10
votes
2
answers
1k
views
Is it known whether $BPP\cap NP\subseteq RP$?
The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
- 101
10
votes
1
answer
259
views
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
- 3,221
10
votes
0
answers
442
views
Expectation of Gowers norm
This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow \...
user1694
9
votes
0
answers
179
views
Pseudorandom object yielding shrinkage in $\ell_p$ norm?
Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
- 651
7
votes
2
answers
437
views
What bound can we get using $k$-th moment inequality under 3-wise independence?
Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)...
- 201
7
votes
1
answer
232
views
Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?
For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}_{y\in Y}({\chi_s(y)})$.
The question I have is, do there exist distributions ...
- 105
7
votes
2
answers
651
views
Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time
I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.
Show that no ...
- 81
7
votes
0
answers
164
views
Where is Yao's original proof that distinguishers imply next-bit-predictors?
In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...
- 1,733
6
votes
1
answer
130
views
Average-case analogue of Small-bias Spaces
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-...
- 383
6
votes
1
answer
230
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 ...
- 875
6
votes
0
answers
172
views
Distributions over circuits and N-to-N vs N-to-1 circuits
This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
- 959
5
votes
1
answer
207
views
Simple candidates for pseudorandom permutations?
Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured ...
- 53
5
votes
0
answers
133
views
Largest size for randomness extractor
Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...
- 415
4
votes
1
answer
440
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.
- 697
4
votes
1
answer
259
views
How tight is the XOR lemma?
The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
- 235
4
votes
1
answer
102
views
Is being fooled by limited independence preserved by products?
Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\...
- 2,743
4
votes
1
answer
294
views
Special properties of bipartite expanders
It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc.
However, I am curious if there are any special properties of ...
- 2,295
4
votes
1
answer
150
views
Strong seeded randomness extractors with low entropy loss
I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.
Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
- 141
4
votes
1
answer
238
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 ...
user6973
4
votes
0
answers
90
views
How many bits are required to sample an almost pairwise independent hash function?
A family of functions $\mathcal{H} = \{ h\colon \{0,1\}^n \to \{0,1\}^m \}$ is said to be $\varepsilon$-almost pairwise independent if, for every distinct $x_1,x_2 \in \{0,1\}^n$ and (not necessarily ...
- 41
4
votes
0
answers
149
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 ...
- 1,645
4
votes
0
answers
94
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 ...
- 1,052
4
votes
0
answers
128
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 ...
- 1,443
3
votes
1
answer
95
views
Optimal random bits complexity for universal hashing
Let $Q_N:=\{0,1\}^N$ denote the $N$-dimensional Hamming cube. Let $a\in Q^N$ and $X\sim\mathrm{Unif}(Q^M)$ be input and random bits respectively, and function $f$ maps the the joint space to the $P$-...
- 639
3
votes
1
answer
151
views
Algebraic construction of $\varepsilon$-biased sets
Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to ...
- 83
3
votes
0
answers
64
views
Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
- 431
2
votes
4
answers
578
views
Algorithmic distinctions between random and pseudorandom.
Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:
$f(r(),r()) = 1$ almost always.
$f(q(),...
- 221
2
votes
1
answer
274
views
n irrational number whose digits are pseudo-random: conceptual mismatch?
Are there irrational numbers whose digits are considered pseudo-random?
Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a ...
- 29
2
votes
1
answer
172
views
On the definition of pseudoentropy
$\mathbf{Definition.}$ A random variable $X$ has pseudoentropy $k$ if it is computationally indistinguishable from a random variable $Y$ with $H(Y) = k$, where $H(Y)$ is the Shannon entropy of $Y$.
...
- 23
2
votes
1
answer
55
views
Can polynomial sized DNF be used to construct weak PRF
Let $F_x : \{0;1\}^n \rightarrow \{0;1\}$ be a family of polyomially sized DNF (with respect to $n$). The key $x$ lives in $\{0;1\}^{\lambda(n)}$, $\lambda(n)$ is polynomially bounded in $n$.
Can such ...
- 109
2
votes
0
answers
90
views
Scaled down and scaled up versions of Impagliazzo-Wigderson Therem
A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP.
When can we change $P$ with some ...
- 1,052
2
votes
0
answers
123
views
k-wise Independence vs. Min-entropy
A distribution $D$ on $\{0,1\}^n$ is $k$-wise independent if any $k$ of the underlying $n$ random variables are independent and each is uniformly distributed.
To me this looks similar in spirit to $D$ ...
- 21
2
votes
0
answers
120
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 ...
- 201
2
votes
0
answers
491
views
Expanded use of an LFSR?
We want an algorithm for the following task:
We are given $n$ and $i$ and we want to check if an $n$-bit LFSR with the sub-register exactly $n/2$ and an interval of $i$ "works". We say an ...
- 203
1
vote
3
answers
711
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\}^{2k}...
user3690
1
vote
0
answers
82
views
Random variates generation in discrete-event simulation models
In discrete-event simulation, most university textbooks (e.g., Law & Kelton, Banks etc.) state that for generating variates for each random variable (e.g., interarrival time, service time etc.) in ...
- 21
1
vote
0
answers
93
views
Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity
In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing
http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf .
I don't state the full lemma ...
- 11
1
vote
0
answers
122
views
Time complexity of polynomial regression with random coefficients
Suppose that I have
$$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$
where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, ...
- 11
1
vote
0
answers
225
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 ...
- 644