Questions tagged [pseudorandomness]
The pseudorandomness tag has no usage guidance.
60 questions
0
votes
1
answer
143
views
Parity of the sum of pseudorandom bits over a non-sparse set of inputs
Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse,...
- 379
1
vote
0
answers
66
views
Constructing lossless conductors using zigzag product - a doubt
Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
- 91
1
vote
0
answers
69
views
Circuit depth of linear algebra operations
I was checking the following paper [1] about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not ...
- 161
2
votes
1
answer
93
views
Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?
This is likely a very silly question which has a simple answer. As I understand, ML models are able to detect patterns in sequences. Given a sequence which is not truly random but rather only ...
- 121
1
vote
0
answers
54
views
AM-protocol when Merlin does not know the input
In classical interactive protocols we assume that Merlin knows Arthur's input $x$.
However we can consider a model where it is not a case. I think that this model is more powerful than classical.
The ...
- 2,023
2
votes
1
answer
70
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 ...
- 341
4
votes
0
answers
155
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
10
votes
0
answers
294
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,763
1
vote
0
answers
118
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
3
votes
1
answer
101
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$-...
- 689
4
votes
1
answer
288
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, ...
- 245
12
votes
1
answer
536
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,491
3
votes
1
answer
152
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
4
votes
1
answer
216
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
1
vote
0
answers
106
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
3
votes
0
answers
69
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
6
votes
1
answer
134
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} [ (-...
- 393
2
votes
0
answers
98
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,072
1
vote
0
answers
155
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
4
votes
0
answers
159
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 ...
- 2,023
4
votes
0
answers
97
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,072
4
votes
0
answers
173
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,453
10
votes
1
answer
471
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,103
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
1
vote
0
answers
354
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 ...
- 654
1
vote
0
answers
113
views
Extractor with somewhat corrupted seeds
In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, ...
- 161
0
votes
1
answer
64
views
Upper bound on the pseudoentropy of any distribution
From here:
The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is ...
1
vote
0
answers
253
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| \...
- 161
2
votes
1
answer
278
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
5
votes
1
answer
222
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
4
votes
1
answer
326
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
2
votes
0
answers
129
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
0
votes
3
answers
253
views
How are random numbers structure-less?
I'm using random numbers for simulations. The main reason is to have an input sequence where no (simulation) algorithm is going to lock on a pattern and introduce unwanted effects into the simulation. ...
- 147
12
votes
2
answers
449
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
6
votes
1
answer
255
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 ...
- 905
25
votes
1
answer
817
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 ...
- 461
2
votes
1
answer
296
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
4
votes
1
answer
107
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,813
5
votes
0
answers
138
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 ...
- 435
7
votes
1
answer
246
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
4
votes
1
answer
524
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.
- 661
2
votes
0
answers
125
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
7
votes
2
answers
524
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
10
votes
1
answer
275
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,313
16
votes
3
answers
438
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
7
votes
2
answers
699
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
18
votes
2
answers
1k
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,888
9
votes
0
answers
180
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
4
votes
1
answer
246
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
0
votes
1
answer
267
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 ...
