A paper by CS Assistant Professor Eshan Chattopadhyay and David Zuckerman of the University of Texas at Austin was accepted for publication in the Annals of Mathematics, the most prestigious journal in mathematics. The paper, entitled “Explicit Two-Source Extractors and Resilient Functions,” previously won the Best Paper Award at the Symposium on the Theory of Computing (STOC) in 2016.
In their paper, Chattopadhyay and Zuckerman present a new method for combining two weak random sources to obtain bits that are almost perfectly random. Among the applications of this discovery is an improved explicit construction of “Ramsey graphs,” a challenging problem in pure mathematics that originated in a paper by the famous Hungarian mathematician Paul Erdős, and that remains unsolved more than sixty years later.