<p>There are some recent works on this topic, for example <a href="https://eccc.weizmann.ac.il/report/2019/099/" rel="nofollow noreferrer">[DMOZ20]</a>, <a href="https://eccc.weizmann.ac.il/report/2020/148/" rel="nofollow noreferrer">[CT21a]</a>, and <a href="https://eccc.weizmann.ac.il/report/2021/080/" rel="nofollow noreferrer">[CT21b]</a>.</p>
<p>For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (something similar to E requires <span class="math-container">$2^{\Omega(n)}$</span>-size circuits, but quantitatively stronger; and plus OWFs exist), BPTIME[<span class="math-container">$T$</span>] is contained in TIME[<span class="math-container">$T \cdot n^{1+o(1)}$</span>], and this factor of <span class="math-container">$n$</span> is tight under an assumption caled NSETH (Nondeterministic Strong Exponential Time Hypothesis).</p>
<p>For average-case derandomization (say over uniform distribution) as you mentioned, [CT21a] also showed that under similar assumptions you can derandomize BPTIME[<span class="math-container">$T$</span>] in TIME[<span class="math-container">$T \cdot n^{o(1)}$</span>] in average. I beleive if you make the assumption significantly stronger you can improve <span class="math-container">$T \cdot n^{o(1)}$</span> to <span class="math-container">$T \cdot \mathrm{polylog}(T)$</span> as you want. [CT21b] also studied average-case derandomization over any polynomial-time samplable distribution.</p>

CC BY-SA 4.0
2023-05-26T23:21:05.820Z
2023-05-26T23:21:05.820Z
Lijie Chen
<p>Many believe derandomization with polynomial overhead, <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span>,
because it follows from <span class="math-container">$2^{\Omega(n)}$</span> circuit lower bounds for <span class="math-container">$\mathsf{E}$</span> (IW97).</p>
<p>Do we have any evidence for or against even stronger (mildly average-case) derandomization?
In particular, I'm interested in the question <span class="math-container">$\mathsf{BPTIME}(t) \subseteq \mathsf{ioHeur}_{\mathsf{o}(1)}\mathsf{DTIME}(t \cdot \log(t)^{\Theta(1)})/\log(t)$</span> for say a quasipolynomial time bound <span class="math-container">$t$</span> but any pointers would be helpful.</p>
<p>The question [https://cstheory.stackexchange.com/questions/39227/fine-grained-complexity-of-bpp] is related but unfortunately unanswered.
The closest connection there would be Dmytro's guess that <span class="math-container">$\mathrm{BPTime}(O(n^a))⊄\mathrm{Time}(O(n^{a+1-ε}))$</span>.</p>

<cc.complexity-theory><derandomization><average-case-complexity>
Fine-grained average-case derandomization
Nicholas Brandt
# Fine-grained average-case derandomization

(Asked by: username_0 on 2023-05-26)

Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$,
because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97).

Do we have any evidence for or against even stronger (mildly average-case) derandomization?
In particular, I'm interested in the question $\mathsf{BPTIME}(t) \subseteq \mathsf{ioHeur}\_{\mathsf{o}(1)}\mathsf{DTIME}(t \cdot \log(t)^{\Theta(1)})/\log(t)$ for say a quasipolynomial time bound $t$ but any pointers would be helpful.

The question [https://cstheory.stackexchange.com/questions/39227/fine-grained-complexity-of-bpp] is related but unfortunately unanswered.
The closest connection there would be Dmytro's guess that $\mathrm{BPTime}(O(n^a))⊄\mathrm{Time}(O(n^{a+1-ε}))$.

**Tags:** cc.complexity-theory, derandomization, average-case-complexity


---

## 1 answers

### Answer by username_1 on 2023-05-26. Score: 3 | Accepted answer

There are some recent works on this topic, for example [[DMOZ20]](https://eccc.weizmann.ac.il/report/2019/099/), [[CT21a]](https://eccc.weizmann.ac.il/report/2020/148/), and [[CT21b]](https://eccc.weizmann.ac.il/report/2021/080/).

For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (something similar to E requires $2^{\Omega(n)}$-size circuits, but quantitatively stronger; and plus OWFs exist), BPTIME[$T$] is contained in TIME[$T \cdot n^{1+o(1)}$], and this factor of $n$ is tight under an assumption caled NSETH (Nondeterministic Strong Exponential Time Hypothesis).

For average-case derandomization (say over uniform distribution) as you mentioned, [CT21a] also showed that under similar assumptions you can derandomize BPTIME[$T$] in TIME[$T \cdot n^{o(1)}$] in average. I beleive if you make the assumption significantly stronger you can improve $T \cdot n^{o(1)}$ to $T \cdot \mathrm{polylog}(T)$ as you want. [CT21b] also studied average-case derandomization over any polynomial-time samplable distribution.


---

