Skip to main content
Share Your Experience: Take the 2024 Developer 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 ...
Dylan McKay's 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)...
William Hoza's user avatar
  • 1,743
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 ...
Thomas's user avatar
  • 2,803
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 ...
Andrew Morgan's user avatar
4 votes

Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

Yes, (it is believed that) there are sequences that can't be learned by any ML model: cryptographic pseudorandom generators (see also here) are one good candidate. If a sequence fails some Diehard ...
D.W.'s user avatar
  • 12.1k
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 ...
Clement C.'s user avatar
  • 4,471
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. ...
guest's user avatar
  • 96
2 votes
Accepted

Parity of the sum of pseudorandom bits over a non-sparse set of inputs

You can't say anything useful. Let $E$ be a pseudorandom permutation on $\{0,1\}^m$ with $n$-bit key, $m$ be large (at least twice the security parameter), $S=\{0,1\}^m$, and define $F$ by $$F(v,w) = ...
D.W.'s user avatar
  • 12.1k
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$, ...
jbapple's user avatar
  • 11.2k
1 vote

Can polynomial sized DNF be used to construct weak PRF

I believe the answer is no, due to "algebraic attacks". That is, take the lowest width (say at most d) term T from the DNF which we denote C. then T(1+C) = 0, where T has low degree < w ...
AnonTCS's user avatar
  • 71
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_\...
user621824's 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 ...
Chris Rutz's user avatar

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