Georgia Institute of Technology School of Mathematics | Georgia Institute of Technology | Atlanta, GA

This thesis consists of four works in dynamical systems with a focus on billiards. In the first part, we consider open dynamical systems, where there exists at least a ``hole" of positive measure in the phase space which some portion of points in phase space escapes through that hole at each iterate of the dynamical system map. Here, we study the escape rate (a quantity that presents at what rate points in phase space escape through the hole) and various estimations of the escape rate of an open dynamical system. We uncover a reason why the escape rate is faster than expected, which is the convexity of the function defining escape rate. Moreover, exact computations of escape rate and its estimations are present for the skewed tent map and Arnold’s cat map.

In the second part of the thesis, we study physical billiards where the moving particle has a finite nonzero size. In contrast to mathematical billiards where a trajectory is excluded when it hits a corner point of the boundary, in physical billiards reflection of the physical particle (a ball) off a visible corner point is well-defined. Initially, we study properties of such reflections in a physical billiards. Our results confirm that the reflection considered in the literature about physical billiards are indeed no-slip friction-free (elastic) collisions.

In the third part of the thesis, we study physical Ehrenfests' wind-tree models, where we show that physical wind-tree models are dynamically richer than the well-known Lorentz gas model. More precisely, when we replace the point particle by a physical one (a ball), the wind-tree models show a new superdiffusive regimes that never been observed in any other model such as Lorentz gas.

Finally, we prove that typical physical polygonal billiard is hyperbolic at least on a subset of positive measure and therefore has a positive Kolmogorov-Sinai entropy for any positive radius of the moving particle.

This dissertation consists of various topics in nonlinear algebra. Particularly, it focuses on solving algebraic problems and polynomial systems through the use of combinatorial tools. We give a broad introduction and discuss connections to applied algebraic geometry, polyhedral, and tropical geometry. The individual topics discussed are as follows:

• Interaction between tropical and classical convexity, with a focus on the tropical convex hull of convex sets and polyhedral complexes. Amongst other results, we characterize tropically convex sets in any dimension, and give a combinatorial description for the dimension of the tropical convex hull of an ordinary affine space. 
• The steady-state degree and mixed volume of a chemical reaction network. We present three case studies of infinite families of networks. For each family, we give a formula for the steady-state degree and mixed volume of the corresponding polynomial system. 
• Methods for finding the solution set of a generic system in a family of polynomial systems with parametric coefficients. We present a framework for describing monodromy-based solvers in terms of decorated graphs. 

Thesis may be viewed here.

BlueJeans link

The probabilistic method is one of the most powerful tools in combinatorics: it has been used to show the existence of many hard-to-construct objects with exciting properties. It also attracts broad interests in designing and analyzing algorithms to find and construct these objects in an efficient way. In this dissertation we obtain four results using algorithmic approaches in probabilistic method:
1. We study the structural properties of the triangle-free graphs generated by a semirandom variant of triangle-free process and obtain a packing extension of Kim’s famous R(3, t) results. This allows us to resolve a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo, and answer a problem in extremal graph theory by Esperet, Kang, and Thomasse.
2. We determine the order of magnitude of Prague dimension, which concerns efficient encoding and decomposition of graphs, of binomial random graph with high probability. We resolve conjectures by Furedi and Kantor. Along the way, we prove a Pippenger-Spencer type edge coloring result for random hypergraphs with edges of size O(log n).
3. We analyze the number set generated by r-AP free process, which answers a problem raised by Li and has connection with van der Waerden number in additive combinatorics and Ramsey theory.
4. We study a refined alteration approach to construct H-free graphs in binomial random graphs, which has applications in Ramsey games.

The Bluejeans link of the defense is https://gatech.bluejeans.com/233874892

Langevin dynamics-based sampling algorithms are arguably among the most widely-used Markov Chain Monte Carlo (MCMC) methods. Two main directions of the modern study of MCMC methods are (i) How to scale MCMC methods to big data applications, and (ii) Tight convergence analysis of MCMC algorithms, with explicit dependence on various characteristics of the target distribution, in a non-asymptotic manner.

This thesis continues the previous efforts in these two lines and consists of three parts. In the first part, we study stochastic gradient MCMC methods for large-scale applications. We propose a non-uniform subsampling of gradients scheme to approximately match the transition kernel of a base MCMC base with full gradient, aiming for better sample quality. The demonstration is based on underdamped Langevin dynamics.

In the second part, we consider an analog of Nesterov's accelerated algorithm in optimization for sampling. We derive a  dynamics termed Hessian-Free-High-Resolution (HFHR) dynamics, from a high-resolution ordinary differential equation description of Nesterov's accelerated algorithm. We then quantify the acceleration of HFHR over underdamped Langevin dynamics at both continuous dynamics level and discrete algorithm level.

In the third part, we study a broad family of bounded, contractive-SDE-based sampling algorithms via mean-square analysis. We show how to extend the applicability of classical mean-square analysis from finite time to infinite time. Iteration complexity in the 2-Wasserstein distance is also characterized and when applied to the Langevin Monte Carlo algorithm, we obtain an improved iteration complexity bound.