- You are here:
- GT Home
- Home
- News & Events

Series: Dissertation Defense

This work studies two topics in sequence analysis. In the first part, we
investigate the large deviations of the shape of the random RSK Young
diagrams, associated with a random word of size n whose letters are
independently drawn from an alphabet of size m=m(n). When the letters are
drawn uniformly and when both n and m converge together to infinity, m
not growing too fast with respect to n, the large deviations of the shape
of the Young diagrams are shown to be the same as that of the spectrum of
the traceless GUE. Since the length of the top row of the Young diagrams is
the length of the longest (weakly) increasing subsequence of the random
word, the corresponding large deviations follow. When the letters are drawn
with non-uniform probability, a control of both highest probabilities will
ensure that the length of the top row of the diagrams satisfies a large
deviation principle. In either case, speeds and rate functions are
identified. To complete this first part, non-asymptotic concentration bounds
for the length of the top row of the diagrams are obtained.
In the second part, we investigate the order of the r-th, 1\le r <
+\infty, central moment of the length of the longest common subsequence of
two independent random words of size n whose letters are identically
distributed and independently drawn from a finite alphabet. When all but one
of the letters are drawn with small probabilities, which depend on the size
of the alphabet, the r-th central moment is shown to be of order
n^{r/2}. In particular, when r=2, the order of the variance is linear.

Series: Dissertation Defense

Please see http://www.aco.gatech.edu/dissert/asadi.html for further details.

Series: Dissertation Defense

Details can be found at http://www.aco.gatech.edu/dissert/postle.html.

Series: Dissertation Defense

This work is concerned with the Almost Axisymmetric Flows with Forcing
Terms which are derived from the inviscid Boussinesq equations. It is our hope that
these
flows will be useful in Meteorology to describe tropical cyclones. We show that
these
flows give rise to a collection of Monge-Ampere equations for which we prove an
existence and uniqueness result. What makes these equations unusual is the boundary
conditions they are expected to satisfy and the fact that the boundary is part of the
unknown. Our study allows us to make inferences in a toy model of the Almost Axisymmetric Flows with
Forcing Terms.

Series: Dissertation Defense

Series: Dissertation Defense

Series: Dissertation Defense

Classical vertex coloring problems ask for the minimum number of colors needed
to color the vertices of a graph, such that adjacent vertices
use different colors. Vertex coloring does have quite a few practical applications
in
communication theory, industry engineering and computer science. Such examples can
be
found in the book of Hansen and Marcotte.
Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem,
even for triangle-free graphs. Intutively, large girth may help reduce the chromatic
number.
However, in 1959, Erdos used the probabilitic method to prove that for any two
positive
integers g and k, there exist graphs of girth at least g and chromatic number at
least k.
Thus, restricting girth alone does not help bound the chromatic number. However, if
we
forbid certain tree structure in addition to girth restriction, then it is possible
to bound the
chromatic number. Randerath determined several such tree structures, and conjectured
that
if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a
star K1,4
with two branches subdivided once.
The main result of this thesis is that Randerath's conjecture is true for graphs
with odd
girth at least 7. We also give an outline of a proof that Randerath's conjecture
holds for
graphs with maximum degree 4.

Series: Dissertation Defense

Series: Dissertation Defense

This dissertation investigates the statistical learning scenarios where a
high-dimensional parameter has to be estimated from a given sample of fixed
size, often smaller than the dimension of the problem.
The first part answers some open questions for the binary classification
problem in the framework of active learning.
Given a random couple (X,Y)\in R^d\times {\pm 1} with
unknown distribution P, the goal of binary classification is to predict a
label Y based on the observation X. The prediction rule is constructed
based on the observations (X_i,Y_i)_{i=1}^n sampled from P.
The concept of active learning can be informally characterized as follows:
on every iteration, the algorithm is allowed to request a label Y for any
instance X which it considers to be the most informative.
The contribution of this work consists of two parts: first, we provide the
minimax lower bounds for performance of the active learning methods under
certain assumptions. Second, we propose an active learning algorithm which
attains nearly optimal rates over a broad class of underlying distributions
and is adaptive with respect to the unknown parameters of the problem.
The second part of this work is related to sparse recovery in the framework
of dictionary learning.
Let (X,Y) be a random couple with unknown distribution P, with X
taking its values in some metric space S and Y - in a bounded subset of
R.
Given a collection of functions H={h_t}_{t\in \mb T}
mapping S to R, the goal of dictionary learning is to construct a
prediction rule for Y given by a linear (or convex) combination of the
elements of H.
The problem is sparse if there exists a good prediction rule that depends on
a small number of functions from H.
We propose an estimator of the unknown optimal prediction rule based on
penalized empirical risk minimization algorithm.
We show that proposed estimator is able to take advantage of the possible
sparse structure of the problem by providing probabilistic bounds for its
performance. Finally, we provide similar bounds in the density estimation
framework.

Series: Dissertation Defense