Empirical Support for Theoretical Conjectures

The PI is engaged in ongoing work on experiments designed to gather evidence for or against conjectures in one or both of two active areas in theoretical computer science: Markov chain Monte Carlo (MCMC) mixing times, and greedy approximation algorithms for combinatorial optimization problems. Research in the area of MCMC mixing seeks to prove theoretical upper and lower bounds on the mixing times—or convergence times—of random walk-based algorithms for sampling from various distributions. The PI has published three papers,,, in 2023, on this research, which were entirely theoretical. Two of these papers2,3—comprising the PI’s dissertation—left open a significant gap between upper and lower theoretical bounds, with some intuition in both cases that the lower bound is more likely correct. The PI is currently working with two MS students, who have implemented code to run a Markov chain for sampling binary trees. The PI has also worked previously with undergraduate students at the University of California, Irvine (UCI), implementing a Markov chain for sampling independent sets in trees. Further work extending this research may give evidence for or against theoretical conjectures regarding the mixing time of this chain. A separate theoretical line of research with opportunities for experiments lies within the broad area of approximation algorithms. We focus on the nearest-neighbor chain technique, which uses a stack-based data structure to speed up greedy algorithms. The PI co-authored a 2019 paper on new applications of the nearest-neighbor