Georgia Institute of Technology College of Sciences

In this informal chat, I will introduce the braid group and several equivalent topological perspectives from which to view it. In particular, we will discuss the role that complex polynomials play in this setting, along with a few classical results.

The Jacobian Conjecture is a famous open problem in commutative algebra and algebraic geometry. Suppose you have a polynomial function $f:\mathbb{C}^n\to\mathbb{C}^n$. The Jacobian Conjecture asserts that if the Jacobian of $f$ is a non-zero constant, then $f$ has a polynomial inverse. Because the conjecture is so easy to state, there have been many claimed proofs that turned out to be false. We will discuss some of these incorrect proofs, as well as several correct theorems relating to the Jacobian Conjecture.

Deep neural networks (DNNs) have revolutionized machine learning by gradually replacing the traditional model-based algorithms with data-driven methods. While DNNs have proved very successful when large training sets are available, they typically have two shortcomings: First, when the training data are scarce, DNNs tend to suffer from overfitting. Second, the generalization ability of overparameterized DNNs still remains a mystery. In this talk, I will discuss two recent works to “inject” the “modeling” flavor back into deep learning to improve the generalization performance and interpretability of the DNN model. This is accomplished by DNN regularization through applied differential geometry and harmonic analysis. In the first part of the talk, I will explain how to improve the regularity of the DNN representation by enforcing a low-dimensionality constraint on the data-feature concatenation manifold. In the second part, I will discuss how to impose scale-equivariance in network representation by conducting joint convolutions across the space and the scaling group. The stability of the equivariant representation to nuisance input deformation is also proved under mild assumptions on the Fourier-Bessel norm of filter expansion coefficients.

The space of degree-n complex polynomials with distinct roots appears frequently and naturally throughout mathematics, but its shape and structure could be better understood. In recent and ongoing joint work with Jon McCammond, we present a deformation retraction of this space onto a simplicial complex with rich structure given by the combinatorics of noncrossing partitions. In this talk, I will describe the deformation retraction and the resulting combinatorial data associated to each generic complex polynomial. We will also discuss a helpful comment from Daan Krammer which connects our work with the ideas of Bill Thurston and his collaborators.

A knot is a smooth embedding of a circle into R^3. Closely related are tangles, which are properly embedded arcs in a 3-ball. We will model certain tangles using jump ropes and relate this to Conway's classification of rational tangles.

For online optimization, the input instance is revealed in a sequence of steps and, after each step, the algorithm has to take an immediate and irrevocable decision based on the previous inputs. Online algorithms produce a sequence of decisions for such problems without the complete information of the future. In the worst-case analysis of online optimization problems, sometimes, it is impossible to achieve any bounded competitive ratio. An interesting way to bypass these impossibility results is to incorporate a stochastic component into the input model. In the random-order arrival model, the adversary specifies an input instance in advance but the input appears according to a random permutation. The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. In this talk, we will present improved competitive algorithms under random-order arrival for these two problems. This is joint work with Susanne Albers and Leon Ladewig.

A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. In the context of genomics, DOWs and operations on DOWs have been used in studies of DNA rearrangement. By modeling the DNA rearrangement process using DOWs, it was observed that over 95% of the scrambled genome of the ciliate Oxytricha trifallax could be described by iterative insertions of the ``repeat pattern'' and the ``return pattern''. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w, we characterize the structure of  w which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively.

Back in the year 2000, Christ and Kiselev introduced a useful "maximal trick" in their study of spectral properties of Schro edinger operators.
The trick was completely abstract and only at the level of basic functional analysis and measure theory. Over the years it was reproven,
generalized, and reused by many authors. We will present its recent application in the theory of restriction of the Fourier transform to
surfaces in the Euclidean space.

I will talk about a connection between graph theory and sutured Floer homology. In fact, there is a one to one correspondence between hypergraphs of a planar bipartite graph and the dimension of sutured Floer homology of a complement of a neighborhood of special alternating link In a three sphere. This is based on the work of Juhas, Kalman and Rasmussen.

In the realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. 

Given a Riemannian manifold M, let f be an eigenfunctions f of the Laplacian with respect to some boundary conditions.  A nodal domain associated with f is the maximal connected subset of the domain M  for which the f does not change sign.

Here we examine the discrete cases, namely we consider nodal domains for graphs. Dekel-Lee-Linial shows that for a Erdős–Rényi graph G(n, p), with high probability there are exactly two nodal domains for each eigenvector corresponding to a non-leading eigenvalue.  We prove that with high probability, the sizes of these nodal domains are approximately equal to each other. 

As a direct corollary of this purely combinatorial result, the sensitivity and degree of every boolean function are polynomially related. This solves an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

In the past decade, the catalog of algorithms available to combinatorial optimizers has been substantially extended to settings which allow submodular objective functions. One significant recent result was a tight (1-1/e)-approximation for maximizing a non-negative monotone submodular function subject to a matroid constraint. These algorithmic developments were happening concurrently with research that found a wealth of new applications for submodular optimization in machine learning, recommender systems, and algorithmic game theory.

The related supermodular maximization models also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints and even when the function has a nice structure. For example, the densest subgraph problem - suspected to be highly intractable - can be expressed as a monotonic supermodular function which has a particularly nice form. Namely, the objective can be expressed by a quadratic form $x^T A x$ where $A$ is a non-negative, symmetric, 0-diagonal matrix. On the other hand, when the entries $A(u,v)$ form a metric, it has been shown that the associated maximization problems have constant factor approximations. Inspired by this, we introduce a parameterized class of non-negative functions called meta-submodular functions that can be approximately maximized within a constant factor. This class includes metric diversity, monotone submodular and other objectives appearing in the machine learning and optimization literature. A general meta-submodular function is neither submodular nor supermodular and so its multi-linear extension does not have the nice convexity/concavity properties which hold for submodular functions. They do, however, have an intrinsic one-sided smoothness property which is essential for our algorithms. This smoothness property might be of independent interest.