On Derandomizing Probabilistic Sublinear-Time Algorithms
Marius Zimand · Proceedings - IEEE Conference on Computational Complexity/Proceedings · 2007
There exists a positive constant alphaT(n) lesnalphaand for any problemLisin BPTIME(T(n)), there exists a deterministic algorithm running in poly(T(n)) time which decides L, except for at most a 2-Omega(T(n)logT(n))fraction of inputs of lengthn.