Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
13 votes

Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

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 ...
user avatar
11 votes

$RL=L$ Progress Since 2006

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)...
user avatar
  • 1,733
10 votes

Pseudorandom generator for finite automata

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, ...
user avatar
  • 7,459
8 votes

Average-case analogue of Small-bias Spaces

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 ...
user avatar
  • 2,743
8 votes

n irrational number whose digits are pseudo-random: conceptual mismatch?

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 ...
user avatar
7 votes

Is it known whether $BPP\cap NP\subseteq RP$?

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 ...
user avatar
7 votes

How are random numbers structure-less?

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 ...
user avatar
  • 14.1k
7 votes
Accepted

Pseudorandom generators indistinguishable by uniform deterministic adversaries

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 "...
user avatar
4 votes
Accepted

Simple candidates for pseudorandom permutations?

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 ...
user avatar
  • 10.3k
4 votes

How are random numbers structure-less?

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 ...
user avatar
4 votes
Accepted

How tight is the XOR lemma?

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 ...
user avatar
  • 4,331
3 votes
Accepted

Deterministic error reduction, state-of-the-art?

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. ...
user avatar
  • 96
3 votes
Accepted

On the definition of pseudoentropy

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 ...
user avatar
  • 7,022
3 votes

Is being fooled by limited independence preserved by products?

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 $\...
user avatar
  • 2,743
2 votes
Accepted

Optimal random bits complexity for universal hashing

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$, ...
user avatar
  • 11k
2 votes

Special properties of bipartite expanders

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" ...
user avatar
  • 644
2 votes

Upper bound on the pseudoentropy of any distribution

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)$ ...
user avatar
  • 2,743
1 vote
Accepted

Algebraic construction of $\varepsilon$-biased sets

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_\...
user avatar
1 vote

Strong seeded randomness extractors with low entropy loss

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 ...
user avatar
1 vote

Pseudorandom generator for finite automata

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 ...
user avatar
  • 10.8k

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