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

# Tag Info

### 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

• 2,743
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$, ...
• 11k

### 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" ...
• 644

### 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)$ ...
• 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_\...
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 ...
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 ...
• 10.8k

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