Quickly Derandomizing Some Recent Randomized Algorithms

I plan to show how to count the pairs of orthogonal vectors among $n$ 0-1 vectors in $d = c\log n$ dimensions in \emph{deterministic} $n^{2-1/O(\log c)}$ time. In the full version of the paper/talk, one can also solve all-pairs shortest paths on $n$ nodes in \emph{deterministic} $n^3/2^{\Omega(\sqrt{\log n})}$ time.

These running times essentially match the best known randomized algorithms (up to constants in the appropriate places), and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. We also resolve an open problem of Santhanam by showing that counting $k$-SAT assignments can be done in $2^{n-n/O(k)}$ time, deterministically.

A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, applying small-biased sets and modulus-amplifying polynomials.

Based on joint work with Timothy Chan that will appear in SODA'16.