Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

We show that hitting sets can derandomize any BPP-algorithm.

This gives a positive answer to a fundamental open question in

probabilistic algorithms. More precisely, we present a polynomial

time deterministic algorithm which uses any given hitting set

to approximate the fractions of 1's in the ...
more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>