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

Oded Goldreich

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