All Questions
Tagged with derandomization pseudorandomness
6 questions
3
votes
1
answer
152
views
Algebraic construction of $\varepsilon$-biased sets
Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to ...
- 83
3
votes
0
answers
69
views
Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
- 431
2
votes
0
answers
98
views
Scaled down and scaled up versions of Impagliazzo-Wigderson Therem
A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP.
When can we change $P$ with some ...
- 1,072
10
votes
2
answers
1k
views
Is it known whether $BPP\cap NP\subseteq RP$?
The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
- 101
17
votes
0
answers
325
views
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
- 3,888
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