Certified Hardness vs. Randomness for Log-Space

Edward Pyne, Ran Raz, Wei Zhan

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, memb…