# Can we derandomize subexponential algorithms given P=BPP?

Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms.

Can we say the same about randomized subexp algorithms like number field sieve?

• Have you tried the padding trick? Pad the input so that the algorithm now runs in polynomial time, derandomize it, and then "unpad". – Yuval Filmus Apr 2 '16 at 22:34
• @YuvalFilmus aha so randomized algorithms can always be derandomized (no matter running time)? – user39969 Apr 2 '16 at 22:37
• Padding only works in one direction, though. Try to write this argument formally, and so answer your own question. Also, when I say "derandomize", I mean use the conjecture $P=BPP$. Everything is conditional anyhow. – Yuval Filmus Apr 2 '16 at 22:38
• @YuvalFilmus When you say padding this is what i understand. pad input to make longer so subexp becomes poly in new input and $P=BPP$ implies randomization is not powerful for this new input and removing padding implies $BPSUBEXP$ is same as $SUBEXP$. – user39969 Apr 2 '16 at 22:42
• Right, that's the idea. – Yuval Filmus Apr 2 '16 at 22:43

Derandomization results transfer "upwards" using the technique of padding. Assume $\mathsf{P}=\mathsf{BPP}$. Suppose that some problem $A$ can be solved in randomized superpolynomial time $t(n)$ (which is time-constructible). Let $A'$ be the same problem, but with inputs padded to length $t(n)$. Then $A' \in \mathsf{BPP} = \mathsf{P}$. The following algorithm then solves $A$ in deterministic time $t(n)$: pad the input to length $t(n)$, then apply the polynomial time algorithm for $A'$.