All Questions
Tagged with derandomization space-bounded
4 questions
0
votes
1
answer
139
views
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Modifying following TedP
We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
- 13.3k
10
votes
1
answer
260
views
$BPL$ with polylog random bits is in $L$
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.
My question is ...
- 393
16
votes
1
answer
554
views
Does Nisan's pseudo-random generator relativize?
Nisan proved in "Psuedorandom Generators for Space-Bounded Computation",
that there exists a pseudo-random generator which "fools" space-bounded computations.
Does this construction hold for every ...
17
votes
1
answer
561
views
Fooling arbitrary symmetric functions
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
- 2,492