First-year Ph.D. student Kuikui Liu and professor Shayan Oveis Gharan of the Allen School’s Theory of Computation group earned a Best Paper Award from the Association for Computing Machinery’s 51st annual Symposium on the Theory of Computing (STOC 2019) by presenting a novel approach for counting the bases of matroids and solving a 30-year-old conjecture by Mihail and Vazirani that will have wide-ranging implications for the theory and practice of computation and mathematics. They and their co-authors resolved this fundamental open problem by combining seemingly unrelated areas of mathematics and theoretical computer science, namely Hodge theory for combinatorial geometries, analysis of Markov chains, and high dimensional expanders. The team’s work has a number of real-world applications — from quantifying the reliability of communication networks and error-correcting codes used in data transmission, to performing diverse feature vector selection for training machine learning models.
In their winning paper, “Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid,” Liu, Oveis Gharan, and co-authors Nima Anari of Stanford University and Cynthia Vinzant of North Carolina State University describe the first fully polynomial randomized approximation scheme (FPRAS) for the problem. Their algorithm, which is based on a simple two-step Markov Chain Monte Carlo process, can be applied to counting the bases of any matroid given by an independent set oracle.
The question is relevant to a variety of domains and practical situations that call for the assignment of resources or transmission of information. For example, a company has a set of jobs it needs to complete and a set of machines capable of completing a subset of those jobs. Assuming each machine is assigned one job and taking into account the probability of each machine failing independently, the authors’ approach can be used to obtain an efficient algorithm which approximates up to a 1 percent error the probability that all jobs will be completed. In another example, a sender is transmitting an encrypted message for which there is a certain probability that each bit of the message will be erased independently. Assuming the code is a linear code, the team’s algorithm provides an efficient procedure to approximate up to a 1 percent error the probability that the receiver can recover the erased bits.
In addition to its application in network reliability, data transmission, and machine learning, the approach put forward by Liu, Oveis Gharan, and their collaborators can be used to sample random spanning forests of a graph — a development that will be of great interest to researchers in combinatorics and probability and to those who study credit networks. The researchers also proved in their paper that the bases exchange graph of any matroid has edge expansion of at least 1, affirming the Mihail-Vazirani conjecture first put forward three decades ago.
The team presented its work at the STOC 2019 conference, which is organized by the ACM Special Interest Group on Algorithms and Computation Theory (ACM SIGACT), in Phoenix, Arizona in June. Read the full research paper here.
Congratulations to Kuikui, Shayan, and the entire team!