Title: High-Dimensional Markov Chains and Applications
Date: June 27, 2023
Time: 11:00 AM
Location: TBD and Zoom (https://gatech.zoom.us/j/99981811450)
Advisor:
Dr. Santosh Vempala, College of Computing, Georgia Institute of Technology
Committee:
Dr. Santosh Vempala, College of Computing, Georgia Institute of Technology
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Prasad Tetali, Department of Mathematical Sciences, Carnegie Mellon University
Dr. Dana Randall, College of Computing. Georgia Institute of Technology
Dr. Will Perkins, College of Computing, Georgia Institute of Technology
Reader: Dr. Will Perkins, College of Computing, Georgia Institute of Technology
Thesis draft: https://www.dropbox.com/s/5l9hdvxiehfmf86/Aditi_Laddha_Thesis.pdf?dl=0
Abstract: A Markov chain is a stochastic process satisfying the Markovian property, meaning that future events are independent of the past states given the present state. Markov chains are essential tools for understanding the geometry of subsets of high-dimensional Euclidean space and serve as the foundation for numerous randomized algorithms used in optimization, integration, linear programming, approximate counting, and more. In this study, we use high-dimensional Markov chains to develop efficient algorithms for two significant problems: sampling uniformly from convex bodies and bounding the discrepancy of set systems. We investigate two Markov chain-based algorithms for uniformly sampling convex bodies and introduce novel isoperimetric inequalities to analyze the mixing time of these chains. Additionally, we propose a unified framework for constructive discrepancy minimization by discretizing a Brownian motion-based stochastic process.
