Back to search

Georgia Institute of Technology

High-Dimensional Markov Chains and Applications

Abstract

dc:description.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 form the basis for numerous randomized algorithms used in optimization, integration, linear programming, approximate counting, and more. They also play a crucial role in understanding the geometry of subsets in high-dimensional Euclidean space. In this study, we use high-dimensional Markov chains to develop efficient algorithms for two 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. We propose a unified framework for constructive discrepancy minimization by discretizing a Brownian motion-based stochastic process.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Laddha, Aditi
Advisor dc:contributor.advisor
  • Vempala, Santosh S.
Committee members dc:contributor.committeemember
  • Singh, Mohit
  • Tetali, Prasad
  • Randall, Dana
  • Perkins, Will

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72703

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Laddha, Aditi. High-Dimensional Markov Chains and Applications. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72703