The Allen School has recognized Dhruv Jain (Ph.D., ‘22) and Kuikui Liu (Ph.D., ‘22) with the William Chan Memorial Dissertation Award, which honors graduate dissertations of exceptional merit and is named in memory of the late graduate student William Chan. Jain was chosen for his work in advancing new sound awareness systems for accessibility, while Liu was selected for his work on a new framework for analyzing the Markov Chain Monte Carlo method.
Jain’s dissertation, titled “Sound Sensing and Feedback Techniques for Deaf and Hard of Hearing People,” investigated the creation and use of several sound awareness systems in addition to exploring how d/Deaf and hard-of-hearing (DHH) individuals feel about emerging sound awareness technology. One of the systems included HoloSound, an augmented reality system that provides real-time captioning, sound identity and sound location information to DHH users via a wearable device, as well as HomeSound, an Internet-of-Things system that integrates smart displays throughout the home to sense common sounds and produce a single visualization of sound activity within the household. Jain also led the team that developed SoundWatch, a smartwatch app that provides DHH individuals with better awareness of incoming sounds.
“Beyond accessibility, the technical innovations in the field of sound sensing and feedback proposed in the thesis have wide applications for other high-impact domains,” Jain said. “Some of which include ecological surveys, home-automation, game audio debugging and appliance repairs.”
Allen School professor Jon E. Froehlich and Human Centered Design & Engineering professor and Allen School adjunct professor Leah Findlater co-advised Jain, whose work in the Makeability Lab helped facilitate sound accessibility through systems employing human computer interaction (HCI) and artificial intelligence (AI).
“Dhruv’s dissertation research makes fundamental advances in the design of sound sensing and feedback systems for people who are deaf or hard of hearing,” Froehlich said. “Throughout his dissertation work, Dhruv has worked closely with the DHH community to understand diverse needs and evaluate his systems, including through large online surveys, interviews and field deployments.”
Jain’s own experiences as a DHH individual informed his research and helped shape his focus on the user experience.
“Dhruv’s dissertation not only exemplifies the human-centered design process in the creation of accessible technologies but also makes transformative technical innovations in integrating AI and HCI to improve information access,” Froehlich added. “As a testament to its impact, his work has received multiple paper awards and a Microsoft Research Dissertation Grant, and SoundWatch has been released and downloaded by over 2,000 Android watch users worldwide.”
Jain graduated in July and joined the University of Michigan’s Computer Science and Engineering department as a professor in September. He is also affiliated with the University of Michigan’s School of Information and Department of Family Medicine.
“I am immensely grateful to the Allen School staff and faculty in supporting me throughout my research journey,” Jain said. “Especially my advisors Jon Froehlich and Leah Findlater, committee members Jennifer Mankoff, Jacob Wobbrock and Richard Ladner, and staff members Elise Dorough, Elle Brown, Emma Gebben, Sandy Kaplan, Aaron Timss, Hector Rodriguez and Chiemi Yamaoka.”
Liu’s dissertation, titled “Spectral Independence: A New Tool to Analyze Markov,” revolutionized the classical analysis of the Markov Chain Monte Carlo (MCMC) method. Probability distributions, seen in several fields such as physics, epidemiology and data privacy, today display immense complexity and are often high-dimensional, resulting in exponentially or infinitely large domains. As a result, manipulating the data becomes impractical insofar as the amount of time needed to calculate the possible outcomes would exceed the age of the universe.
The MCMC method, which uses sampling to efficiently estimate otherwise unruly statistics, attempts to tackle this problem. Markov chains act as random agents in a probability distribution that help explain a sequence of possible outcomes. They are used in a variety of fields due to their ease-of-implementation in high-dimensional sampling problems.
But they remain difficult to analyze. Liu’s dissertation introduced spectral independence, a framework for better understanding the MCMC method besides finding elegant solutions from complex, and sometimes chaotic, crossroads.
“Beyond practical motivations, the framework we developed also has intimate connections with beautiful and deep mathematics,” Liu said. “In particular, we also aimed to settle some of the longstanding conjectures at the intersection of pure mathematics, physics, and theoretical computer science — for example, counting certain fundamental combinatorial structures called ‘bases of matroids,’ and sampling from the hardcore gas and Ising models in statistical physics.”
Liu credited professors Shayan Oveis Gharan and Anna Karlin, his advisors in the Allen School’s Theory of Computation group, for providing mentorship and encouragement throughout his research.
“Right now, many experts are trying to absorb and employ Kuikui’s machinery to solve their own research problems,” Oveis Gharan said. “I expect to see these techniques used in areas further away from computer science, such as physics, chemistry or applied mathematics and perhaps even in the social sciences soon.”
Together, Liu and Oveis Gharan and their co-authors earned a Best Paper Award in 2019 from the Association for Computing Machinery’s Symposium on the Theory of Computing (STOC) by presenting a novel approach for counting the bases of matroids. Liu was a first-year Ph.D. student at the time.
Since then, the pair have collaborated on several other projects involving spectral independence, mathematics and statistical physics.
“In my opinion, Kuikui’s thesis is one of the deepest and strongest dissertations to have been produced in all of computer science in the last year, combining beautiful and insightful mathematical proofs with high-impact applications,” Oveis Gharan added. “The interdisciplinary aspect of his thesis makes the results applicable and important to many fields beyond computer science and I am sure that as more scientists learn about it, they will find ways to exploit Kuikui’s techniques in their own research.”
Liu will join the MIT computer science department as a professor in the fall of 2023.
“Thank you so much to the Allen School!” Liu said. “I am immensely grateful for this recognition, and even more so to my mentors Shayan Oveis Gharan and Anna Karlin, my collaborators, our theory group and family and friends for the nurturing environment. It is a reminder of how fortunate I am to be able to work with such incredible researchers. I am honored to be a part of the Allen School community and will miss it dearly.”
Congratulations to DJ and Kuikui!