Allen School professor Shayan Oveis Gharan and Ph.D. alumnus Kuikui Liu, now a professor at MIT, are part of a team of researchers that received this year’s Michael and Sheila Held Prize from the National Academy of Sciences for introducing a new method for counting the bases of matroids. The annual prize honors “outstanding, innovative, creative and influential research” in the field of combinatorial and discrete optimization published in the past eight years.
In their winning paper “Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid,” the researchers bridge three different and unexpected subfields — Hodge theory for matroids and combinatorial geometries, Markov chains analysis and high dimensional expanders — to resolve a 30-year-old conjecture by Mihail and Vazirani, one of the most important open questions in the field of approximate counting. Their work has a number of real-world applications including network reliability, data transmission and machine learning and has led to other notable developments in theoretical computer science.
“We came up with a solution that not only answered an open problem many people had tried for years, but the answer was so simple, elegant, universal and easy to use that it changed the field,” Oveis Gharan said. “Because these different research communities have evolved independently, they have a lot of tools that the other one doesn’t have. Often, you can use tools from one community to answer questions in the other community — which is what we did.”
Oveis Gharan, Liu and their collaborators University of Washington Mathematics professor Cynthia Vinzant and Nima Anari from Stanford University introduced the first fully polynomial randomized approximation scheme (FPRAS) to count the number of bases of any matroid given by an independent set oracle. Their algorithm utilizes the simple two-step Monte Carlo Markov Chain (MCMC) method to address the Mihail-Vazirani conjecture which says that the bases exchange graph of any matroid has edge expansion of at least one.
This algorithm is especially useful in situations that require the assignment of resources or transmission of information such as network reliability problems. For example, if there was a network of routers connected by wires, this algorithm can help estimate the probability that the network gets disconnected based on which wires become independently damaged. These types of problems are usually solved using Markov chains to check if random subnetworks are connected.
However, in most cases it can be very difficult to figure out how long you should run the Markov chain to get the correct answer. The researchers developed a new tool which uses polynomials to analyze the Markov chains, answering the long-standing open problem.
In another example, a company has a certain number of jobs it needs completed along with a set of machines that can do a subset of those jobs. If you assume each machine can only be assigned one job and account for the probability of each machine independently failing, then this method can help generate an efficient algorithm that can approximate the probability that all the jobs will be finished with up to a 1 percent error margin.
This paper is part of a series of research that shows that the generating polynomial of the bases of any matroid is a log-concave function, uses the log-concavity result to prove tight mixing bounds for natural random walks on the bases of matroids and utilizes the log-concavity result to prove the Mason’s conjecture on the log-concavity of the sequence of the number of independent sets of a matroid.
“Since our research came out, there has been a sudden birth of so many papers using our techniques and finding new applications and answering other problems,” Oveis Gharan said. “It’s rare for a theoretician to feel an impact of their work.”
The Held Prize is not the first award Oveis Gharan, Liu and their collaborators have received for their research. The team received the Best Paper Award from the Association for Computing Machinery’s 51st annual Symposium on the Theory of Computing (STOC 2019).
“As far as I am concerned, Shayan’s combination of brilliance, creativity, relentless enthusiasm and generosity are unsurpassed. My collaborations with him have been one of the absolute highlights of my career,” Allen School professor Anna Karlin said.
Read more about the Michael and Sheila Held Prize and the team’s award-winning paper.