AF:Medium:Fine-Grained Derandomization

University Of Texas At Austin, Austin TX

Investigators

Abstract

For many problems, randomized algorithms offer significant speedups over known algorithms that don't use randomness. However, randomization introduces uncertainty in the outcome of the algorithm, as there will be a small probability of error. The purpose of this project is to explore when uncertainty can be eliminated without giving up on speed. The project integrates education and outreach, including mentoring of students, public lectures and popular science writing. The PIs identify several families of problems where randomized algorithms outperform the best known deterministic ones, including: problems on dense graphs like finding an approximate clique in a dense graph; algebraic problems like polynomial identity testing and factorization; and problems that can be solved using Markov chains, like approximately counting the number of perfect matchings in a bipartite graph. The PIs wish to develop new techniques for derandomization that do not increase the run-time substantially. The PIs also want to prove that, under widely believed complexity assumptions, some randomized algorithms are impossible to derandomize without a significant loss in speed.