Algorithms that approximately uniformly generate random combinatorial objects have been the subject of much study. Though these algorithms run in polynomial time, they are quite slow and it is important to speed them up. One way to do so would be to consider using multiple processors to compute a random solution in a parallel or distributed setting. Furthermore, when the input size is huge, it may be desirable to output only the piece of the random object that the user is interested in viewing. In this project we will study new algorithms for parallel/distributed and local (approximate) uniform generation of combinatorial objects. We will consider such algorithms for the following problems: CNF, DNF, Graph Coloring, Hypergraph Coloring, and Discrepancy Minimization.

My interest in this SuperUROP develops from taking 6.842 (Randomness and Computation) in Spring 2020. I was fascinated by the power of randomness and how it can approximate’ hard problems in polynomial time. I have taken some related courses involving algorithms and probability, and I want to apply that knowledge on this project. I want to gain more exposure to the research environment and hope to publish a paper if the result is satisfying.