Questions tagged [pseudorandomness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
61 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,...
aba's user avatar
  • 91
1 vote
0 answers
67 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 ...
terett's user avatar
  • 151
2 votes
1 answer
88 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 ...
AaronYeloy's user avatar
1 vote
0 answers
53 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 ...
Alexey Milovanov's user avatar
2 votes
1 answer
62 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 ...
ULechine's user avatar
  • 149
4 votes
0 answers
129 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 ...
user65356's user avatar
8 votes
0 answers
248 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 ...
William Hoza's user avatar
  • 1,733
1 vote
0 answers
112 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 ...
E-O's user avatar
  • 21
3 votes
1 answer
98 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$-...
AmeerJ's user avatar
  • 679
4 votes
1 answer
282 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, ...
Andy's user avatar
  • 245
12 votes
1 answer
519 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 + ...
Clement C.'s user avatar
  • 4,461
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 ...
user621824's user avatar
4 votes
1 answer
184 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. ...
satya's user avatar
  • 141
1 vote
0 answers
101 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 ...
ron653's user avatar
  • 11
3 votes
0 answers
68 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\}^...
Izaak Meckler's user avatar
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} [ (-...
BharatRam's user avatar
  • 383
2 votes
0 answers
97 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 ...
verifying's user avatar
  • 1,072
1 vote
0 answers
151 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, ...
user46584's user avatar
4 votes
0 answers
155 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 ...
Alexey Milovanov's user avatar
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 ...
verifying's user avatar
  • 1,072
4 votes
0 answers
154 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 ...
gradstudent's user avatar
  • 1,443
10 votes
1 answer
458 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 ...
Thomas Klimpel's user avatar
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?
bppcapnpvsrp's user avatar
1 vote
0 answers
315 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 ...
Student's user avatar
  • 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, ...
Xi Wu's user avatar
  • 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 ...
user34954's user avatar
1 vote
0 answers
243 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| \...
Xi Wu's user avatar
  • 161
2 votes
1 answer
244 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$. ...
user34061's user avatar
5 votes
1 answer
219 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 ...
Adam Lelkes's user avatar
4 votes
1 answer
318 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 ...
Joe Bebel's user avatar
  • 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$ ...
user32331's user avatar
0 votes
3 answers
246 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. ...
Gere's user avatar
  • 147
12 votes
2 answers
423 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 ...
Holden Lee's user avatar
6 votes
1 answer
245 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 ...
Pteromys's user avatar
  • 895
25 votes
1 answer
746 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 ...
ruadath's user avatar
  • 441
2 votes
1 answer
289 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 ...
mathersjj1's user avatar
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)]\...
Thomas's user avatar
  • 2,803
5 votes
0 answers
136 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 ...
SAmath's user avatar
  • 425
7 votes
1 answer
243 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 ...
Akshay's user avatar
  • 105
4 votes
1 answer
516 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.
Omar Shehab's user avatar
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 ...
Amos's user avatar
  • 201
7 votes
2 answers
512 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)...
Amos's user avatar
  • 201
10 votes
1 answer
267 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 ...
Geoffrey Irving's user avatar
16 votes
3 answers
428 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(...
user12484's user avatar
  • 163
7 votes
2 answers
682 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 ...
eof's user avatar
  • 81
18 votes
2 answers
977 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 ...
Henry Yuen's user avatar
  • 3,788
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)-...
Zeyu's user avatar
  • 651
4 votes
1 answer
243 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 ...
user avatar
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 ...
Golmokorov's user avatar
17 votes
0 answers
320 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 ...
Henry Yuen's user avatar
  • 3,788