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 ...
- 548
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)...
- 1,733
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 ...
- 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 ...
- 1,429
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 ...
- 11.7k
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 ...
- 4,451
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. ...
- 96
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$, ...
- 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
...
- 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_\...
- 83
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 ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible