13

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first") ...


11

If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support. Theorem. Let $H(Y)$ be the Shannon entropy of $Y$ and let $F \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$. Proof. Consider the collision ...


11

One line of work has shown how to improve the analysis of the classic INW PRG for the special cases of fooling regular and permutation branching programs. The seed length is only $\widetilde{O}(\log n)$ or $O(\log n)$ in some cases. [LRTV09] [BV10] [De11] [KNP11] [Ste12] [BRRY14] [HPV21] Another line of work has developed a PRG framework based on iterated ...


10

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known. But if $d$ is very small, say a constant, then you can do better and achieve logarithmic seed length -- I think, this is something I thought about years ago but never wrote down. The trick is to use ...


8

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior. Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (...


8

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case. Unfortunately, as you will see,...


7

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\...


7

I can give several answers to your question. Algorithmic randomness. When should we call a sequence $x_1,\ldots,x_n$ of bits random? A priori, all sequences have the same probability, so it's not clear on what grounds we should single out one sequence or another as not being random. This is partly a philosophical question, but "applied philosophy" has given ...


7

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm ...


6

The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.


4

Yes. The following paper presents a candidate for a PRF that is implementable in $NC^1$, whose security is based on a lattice assumption (hardness of LWE): Abhishek Banerjee, Chris Peikert, Alon Rosen. Pseudorandom Functions and Lattices. EUROCRYPT 2012. It also has some discussion of related literature that might be helpful. Also, here are two trivial ...


4

Although the previous answers are fairly comprehensive, let me just add that there are notions of time-bounded Kolmogorov complexity which can apply in your situation. For example, $K^t(x)$ is the length of the shortest program that produces $x$ within time $t(|x|)$. So, for example, a pseudorandom number generator that takes time $n^3$ could still produce ...


4

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions: Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$. Such functions are known to exist; see, e.g., Chapter 6....


3

I have figured out that the answer to this question is yes. The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)


3

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions. In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is ...


3

Yes, we can always say that $X$ has pseudoentropy at least $H(X)$. You can take $Y$ to be a completely separate, independent random variable that has the same distribution as $X$. Then $X$ and $Y$ are computationally indistinguishable (indeed they are "completely" indistinguishable): $\Pr[A(X) = 1] = \Pr[A(Y) = 1]$ for all algorithms $A$. Instead of ...


2

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.


2

Take any distribution $D$ on $\{0,1\}^n$. Sample $k(n)$ points $x_1, \cdots, x_{k(n)}$ independently from $D$ and let $\tilde D$ be the uniform distribution that gives a random $x_i$. Then, if $k(n)$ is super-polynomially large e.g. $k=n^{\log n}$, you cannot distinguish $D$ and $\tilde D$ using only $\mathrm{poly}(n)$ samples. Hence $D$ is computationally ...


2

Two things come to mind when I hear "bipartite expanders" The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all ...


1

recall that $$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$ if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have $$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$ So, observe that whenever $p_\tau(x,y)\neq 0$ we win as $z$ is uniform and the expected value of $f_{p_\tau(x,y)}(z)$ is also $1/2$ which means ...


1

I'm not sure if this is what you are looking for, but as I recall, there is a mathematical proof that AMLS (advanced multi-level strategy) is maximal. This document does not contain the proof, but an outline of it is on page 9: Coin Toss As a practical example, I seed AMLS with timer output to update a hashed accumulator used for seeding a reference PRNG, ...


1

something close to what you are requesting seems to be proven in Thm 2.10 p6 of these lecture notes by O'Donnell, Lecture 16: Nisan’s PRG for small space but it does not cite the original ref for the proof. a simple statement of the theorem in terms of FSMs is not given in this ref but is translatable. (volunteers?) in the theorem $M^n$ is a transition ...


Only top voted, non community-wiki answers of a minimum length are eligible