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

Series: ACO Student Seminar

Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Minimum s-t Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization.

Here, we are given a graph with edges labeled + or - and the goal is to produce a clustering that agrees with the labels as much as possible: + edges within clusters and - edges across clusters.

The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a global objective, e.g., minimizing the total number of disagreements or maximizing the total number of agreements.

We depart from this and study local objectives: minimizing the maximum number of disagreements for edges incident on a single node, and the analogous max min agreements objective.

This naturally gives rise to a family of basic min-max graph cut problems.

A prototypical representative is Min-Max s-t Cut: find an s-t cut minimizing the largest number of cut edges incident on any node.

In this talk we will give a short introduction of Correlation Clustering and discuss the following results:

- an O(\sqrt{n})-approximation for the problem of minimizing the maximum total weight of disagreement edges incident on any node (thus providing the first known approximation for the above family of min-max graph cut problems)
- a remarkably simple 7-approximation for minimizing local disagreements in complete graphs (improving upon the previous best known approximation of 48)
- a (1/(2+epsilon))-approximation for maximizing the minimum total weight of agreement edges incident on any node, hence improving upon the (1/(4+epsilon))-approximation that follows from the study of approximate pure Nash equilibria in cut and party affiliation games.

Joint work with Moses Charikar and Neha Gupta.

Series: Stochastics Seminar

We present the joint distribution of the Busemann functions, in all directions of growth, of the exactly solvable corner growth model (CGM). This gives a natural coupling of all stationary CGMs and leads to new results about geodesics. Properties of this joint distribution are accessed by identifying it as the unique invariant distribution of a multiclass last passage percolation model. This is joint work with Timo Seppäläinen.

Series: High Dimensional Seminar

Linear Schur multipliers, which act on matrices by entrywisemultiplications, as well as their generalizations have been studiedfor over a century and successfully applied in perturbation theory (asdemonstrated in the previous talk). In this talk, we will discussestimates for finite dimensional multilinear Schur multipliersunderlying these applications.

Series: Analysis Seminar

Linear Schur multipliers, which act on matrices by entrywisemultiplications, as well as their generalizations have been studiedfor over a century and successfully applied in perturbation theory. Inthis talk, we will discuss extensions of Schur multipliers tomultilinear infinite dimensional transformations and then look intoapplications of the latter to approximation of operator functions.

Series: Research Horizons Seminar

An element of the braid group can be visualized as a collection of n strings that are braided (like a hair braid). Braid groups are ubiquitous in mathematics in science, as they record the motions of a number of points in the plane. These points can be autonomous vehicles, particles in a 2-dimensional medium, or roots of a polynomial. We will give an introduction to and a survey of braid groups, and discuss what is known about homomorphisms between braid groups.

Series: Mathematical Biology Seminar

Inference of evolutionary dynamics of heterogeneous cancer and viral populations Abstract: Genetic diversity of cancer cell populations and intra-host viral populations is one of the major factors influencing disease progression and treatment outcome. However, evolutionary dynamics of such populations remain poorly understood. Quantification of selection is a key step to understanding evolutionary mechanisms driving cancer and viral diseases. We will introduce a mathematical model and an algorithmic framework for inference of fitness landscapes of heterogeneous populations from genomic data. It is based on a maximal likelihood approach, whose objective is to estimate a vector of clone/strain fitnesses which better fits the observed tumor phylogeny, observed population structure and the dynamical system describing evolution of the population as a branching process. We will discuss our approach to solve the problem by transforming the original continuous maximum likelihood problem into a discrete optimization problem, which could be considered as a variant of scheduling problem with precedent constraints and with non-linear cumulative cost function.

Series: Stochastics Seminar

Wiener-Hopf factorization (WHf) encompasses several important results in probability and stochastic processes, as well as in operator theory. The importance of the WHf stems not only from its theoretical appeal, manifested, in part, through probabilistic interpretation of analytical results, but also from its practical applications in a wide range of fields, such as fluctuation theory, insurance and finance. The various existing forms of the WHf for Markov chains, strong Markov processes, Levy processes, and Markov additive process, have been obtained only in the time-homogeneous case. However, there are abundant real life dynamical systems that are modeled in terms of time-inhomogenous processes, and yet the corresponding Wiener-Hopf factorization theory is not available for this important class of models. In this talk, I will first provide a survey on the development of Wiener-Hopf factorization for time-homogeneous Markov chains, Levy processes, and Markov additive processes. Then, I will discuss our recent work on WHf for time-inhomogensous Markov chains. To the best of our knowledge, this study is the first attempt to investigate the WHf for time-inhomogeneous Markov processes.

Series: PDE Seminar

I will first give a short introduction of the Navier-Stokes equations, then review some previous results on theconditional regularity of solutions to the incompressible Navier-Stokes equations in the critical Lebesguespaces, and finally discuss some recent work which mainly addressed the boundary regularity issue.

Series: Geometry Topology Seminar

Any knot in $S^3$ may be reduced to a slice knot by making some crossing changes. Indeed, this slice knot can be taken to be the unknot. We show that the same is true of knots in homology spheres, at least topologically. Something more complicated is true smoothly, as not every homology sphere bounds a smooth simply connected homology ball. We prove that a knot in a homology sphere is null-homotopic in a homology ball if and only if that knot can be reduced to the unknot by a sequence of concordances and crossing changes. We will show that there exist knot in a homology sphere which cannot be reduced to the unknot by any such sequence. As a consequence, there are knots in homology spheres which are not concordant to those examples produced by Levine in 2016 and Hom-Lidman-Levine in 2018.

Series: Other Talks

Georgia Tech is leading the way in Creating the Next in higher education.In this talk I will present (1) My vision for ACO and (2) how my research relates naturally to ACO both where the A,C,O fields are going, and my own specific interests