## Seminars and Colloquia by Series

### Discrete Optimal Transport With Applications in Path Planning and Data Clustering

Series
Dissertation Defense
Time
Wednesday, April 17, 2019 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Haoyan ZhaiGeorgia Tech

Optimal transport is a thoroughly studied field in mathematics and introduces the concept of Wasserstein distance, which has been widely used in various applications in computational mathematics, machine learning as well as many areas in engineering. Meanwhile, control theory and path planning is an active branch in mathematics and robotics, focusing on algorithms that calculates feasible or optimal paths for robotic systems. In this defense, we use the properties of the gradient flows in Wasserstein metric to design algorithms to handle different types of path planning and control problems as well as the K-means problems defined on graphs.

### Legendrian Large Cables

Series
Dissertation Defense
Time
Tuesday, April 9, 2019 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andrew McCulloughGeorgia Institute of Technology

We define the notion of a knot type having Legendrian large cables and
show that having this property implies that the knot type is not uniformly thick.
Moreover, there are solid tori in this knot type that do not thicken to a solid torus
with integer sloped boundary torus, and that exhibit new phenomena; specifically,
they have virtually overtwisted contact structures. We then show that there exists
an infinite family of ribbon knots that have Legendrian large cables. These knots fail
to be uniformly thick in several ways not previously seen. We also give a general
construction of ribbon knots, and show when they give similar such examples.

### Text-classification methods and the mathematical theory of Principal Components

Series
Dissertation Defense
Time
Monday, April 8, 2019 - 12:10 for 1.5 hours (actually 80 minutes)
Location
Skiles 202
Speaker
Jiangning ChenGeorgia Institute of Technology

We are going talk about three topics. First of all, Principal Components Analysis (PCA) as a dimension reduction technique. We investigate how useful it is for real life problems. The problem is that, often times the spectrum of the covariance matrix is wrongly estimated due to the ratio between sample space dimension over feature space dimension not being large enough. We show how to reconstruct the spectrum of the ground truth covariance matrix, given the spectrum of the estimated covariance for multivariate normal vectors. We then present an algorithm for reconstruction the spectrum in the case of sparse matrices related to text classification.

In the second part, we concentrate on schemes of PCA estimators. Consider the problem of finding the least eigenvalue and eigenvector of ground truth covariance matrix, a famous classical estimator are due to Krasulina. We state the convergence proof of Krasulina for the least eigenvalue and corresponding eigenvector, and then find their convergence rate.

In the last part, we consider the application problem, text classification, in the supervised view with traditional Naive-Bayes method. We find out an updated Naive-Bayes method with a new loss function, which loses the unbiased property of traditional Naive-Bayes method, but obtains a smaller variance of the estimator.

Committee:  Heinrich Matzinger (Advisor); Karim Lounici (Advisor); Ionel Popescu (school of math); Federico Bonetto (school of math); Xiaoming Huo (school of ISYE);

### Comparison of sequences generated by a hidden Markov model

Series
Dissertation Defense
Time
Tuesday, March 12, 2019 - 13:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
George KerchevGeorgia Tech
The length LC_n of the longest common subsequences of two strings X = (X_1, ... , X_n) and Y = (Y_1, ... , Y_n) is a way to measure the similarity between X and Y. We study the asymptotic behavior of LC_n when the two strings are generated by a hidden Markov model (Z, (X, Y)) and we build upon asymptotic results for LC_n obtained for sequences of i.i.d. random variables. Under some standard assumptions regarding the model we first prove convergence results with rates for E[LC_n]. Then, versions of concentration inequalities for the transversal fluctuations of LC_n are obtained. Finally, we outline a proof for a central limit theorem by building upon previous work and adapting a Stein's method estimate.

### Coloring graphs with no K5-subdivision: disjoint paths in graphs

Series
Dissertation Defense
Time
Tuesday, March 12, 2019 - 10:00 for 1.5 hours (actually 80 minutes)
Location
203 Classroom D.M. Smith
Speaker
Qiqin XieGeorgia Institute of Technology
The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos' conjecture for k >= 6. It is not hard to prove that the conjecture is true for k <= 3. Hajos' conjecture remains open for k = 4 and k = 5. We consider a minimal counterexample to Hajos' conjecture for k = 4: a graph G, such that G contains no K_5-subdivision, G is not 4-colorable, and |V (G)| is minimum. We use Hajos graph to denote such counterexample. One important step to understand graphs containing K_5-subdivisions is to solve the following problem: let H represent the tree on six vertices, two of which are adjacent and of degree 3. Let G be a graph and u1, u2, a1, a2, a3, a4 be distinct vertices of G. When does G contain a topological H (i.e. an H-subdivision) in which u1, u2 are of degree 3 and a1, a2, a3, a4 are of degree 1? We characterize graphs with no topological H. This characterization is used by He, Wang, and Yu to show that graph containing no K_5-subdivision is planar or has a 4-cut, establishing conjecture of Kelmans and Seymour. Besides the topological H problem, we also obtained some further structural information of Hajos graphs.

### Dynamics of Religious Group Growth and Survival

Series
Dissertation Defense
Time
Friday, June 29, 2018 - 13:00 for 2 hours
Location
Skiles 005
Speaker
Tongzhou ChenSchool of Mathematics
We model and analyze the dynamics of religious group membership and size. A groups is distinguished by its strictness, which determines how much time group members are expected to spend contributing to the group. Individuals differ in their rate of return for time spent outside of their religious group. We construct a utility function that individ- uals attempt to maximize, then find a Nash Equilibrium for religious group participation with a heterogeneous population. We then model dynamics of group size by including birth, death, and switching of individuals between groups. Group switching depends on the strictness preferences of individuals and their probability of encountering members of other groups. We show that in the case of only two groups one with finite strictness and the other with zero there is a clear parameter combination that determines whether the non-zero strictness group can survive over time, which is more difficult at higher strictness levels. At the same time, we show that a higher than average birthrate can allow even the highest strictness groups to survive. We also study the dynamics of several groups, gaining insight into strategic choices of strictness values and displaying the rich behavior of the model. We then move to the simultaneous-move two-group game where groups can set up their strictnesses strategically to optimize the goals of the group. Affiliations are assumed to have three types and each type of group has its own group utility function. Analysis on the utility functions and Nash equilibria presents different behaviors of various types of groups. Finally, we numerically simulated the process of new groups entering the reli- gious marketplace which can be viewed as a sequence of Stackelberg games. Simulation results show how the different types of religious groups distinguish themselves with regard to strictness.

### Geometric Bijections of Graphs and Regular Matroids​

Series
Dissertation Defense
Time
Tuesday, June 26, 2018 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chi Ho YuenGeorgia Tech
The Jacobian of a graph, also known as the sandpile group or the critical group, is a finite group abelian group associated to the graph; it has been independently discovered and studied by researchers from various areas. By the Matrix-Tree Theorem, the cardinality of the Jacobian is equal to the number of spanning trees of a graph. In this dissertation, we study several topics centered on a new family of bijections, named the geometric bijections, between the Jacobian and the set of spanning trees. An important feature of geometric bijections is that they are closely related to polyhedral geometry and the theory of oriented matroids despite their combinatorial description; in particular, they can be generalized to Jacobians of regular matroids, in which many previous works on Jacobians failed to generalize due to the lack of the notion of vertices.

### Topics on the longest common subsequences: Simulations, computations, and Variance

Series
Dissertation Defense
Time
Friday, June 22, 2018 - 13:30 for 2 hours
Location
Skiles 005
Speaker
Qingqing LiuGeorgia Tech
The study of the longest common subsequences (LCSs) of two random words is a classical problem in computer science and bioinformatics. A problem of particular probabilistic interest is to determine the limiting behavior of the expectation and variance of the length of the LCS as the length of the random words grows without bounds. This dissertation studies the problem using both Monte-Carlo simulation and theoretical analysis. The specific problems studied include estimating the growth order of the variance, LCS based hypothesis testing method for sequences similarity, theoretical upper bounds for the Chv\'atal-Sankoff constant of multiple sequences, and theoretical growth order of the variance when the two random words have asymmetric distributions.

### Topics in percolation and sequence analysis

Series
Dissertation Defense
Time
Friday, June 22, 2018 - 11:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
Chen XuGeorgia Tech
We will present three results in percolation and sequence analysis. In the first part, we will briefly show an exponential concentration inequality for transversal fluctuation of directed last passage site percolation. In the the second part, we will dive into the power lower bounds for all the r-th central moments ($r\ge1$) of the last passage time of directed site perolcation on a thin box. In the last part, we will partially answer a conjecture raised by Bukh and Zhou that the minimal expected length of the longest common subsequences between two i.i.d. random permutations with arbitrary distribution on the symmetric group is obtained when the distribution is uniform and thus lower bounded by $c\sqrt{n}$ by showing that some distribution can be iteratively constructed such that it gives strictly smaller expectation than uniform distribution and a quick cubic root of $n$ lower bound will also be shown.

### The Back-and-Forth Error Compensation and Correction Method for Linear Hyperbolic Systems and a Conservative BFECC Limiter

Series
Dissertation Defense
Time
Friday, June 22, 2018 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles Building 114 (Conference Room 114)
Speaker
Xin WangSchool of Mathematics, Georgia Institute of Technology
In this dissertation, we studied the Back and Forth Error Compensation and Correction (BFECC) method for linear hyperbolic PDE systems and nonlinear scalar conservation laws. We extend the BFECC method from scalar hyperbolic PDEs to linear hyperbolic PDE systems, and showed similar stability and accuracy improvement are still valid under modest assumptions on the systems. Motivated by this theoretical result, we propose BFECC schemes for the Maxwell's equations. On uniform orthogonal grids, the BFECC schemes are guaranteed to be second order accurate and have larger CFL numbers than that of the classical Yee scheme. On non-orthogonal and unstructured grids, we propose to use a simple least square local linear approximation scheme as the underlying scheme for the BFECC method. Numerical results showed the proposed schemes are stable and are second order accurate on non-orthogonal grids and for systems with variable coefficients. We also studied a conservative BFECC limiter that reduces spurious oscillations for numerical solutions of nonlinear scalar conservation laws. Numerical examples with the Burgers' equation and KdV equations are studied to demonstrate effectiveness of this limiter.