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 >>>

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 >>>

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph.
One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and ... more >>>