All Seminars
| Title: On Spanning Trees with few Branch Vertices |
|---|
| Defense: Dissertation |
| Speaker: Warren Shull of Emory University |
| Contact: Warren Shull, warren.edward.shull@emory.edu |
| Date: 2018-03-05 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Hamiltonian paths, which are a special kind of spanning tree, have long been of interest in graph theory and are notoriously hard to compute. One notable feature of a Hamiltonian path is that all its vertices have degree two in the path. In a tree, we call vertices of degree at least three \emph{branch vertices}. If a connected graph has no Hamiltonian path, we can still look for spanning trees that come "close," in particular by having few branch vertices (since a Hamiltonian path would have none). \bigskip A conjecture of Matsuda, Ozeki, and Yamashita posits that, for any positive integer $k$, a connected claw-free $n$-vertex graph $G$ must contain either a spanning tree with at most $k$ branch vertices or an independent set of $2k+3$ vertices whose degrees add up to at most $n-3$. In other words, $G$ has this spanning tree whenever $\sigma_{2k+3}(G)\geq n-2$. We prove this conjecture, which was known to be sharp. |
| Title: Numerical and Streaming Analyses of Centrality Measures on Graphs |
|---|
| Seminar: Numerical Analysis and Scientific Computing |
| Speaker: Eisha Nathan of Georgia Institute of Technology |
| Contact: Michele Benzi, mbenzi@emory.edu |
| Date: 2018-03-02 at 2:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Graphs are a natural representation for modeling relationships between entities across many different fields of research. In real-world networks today, new data is constantly being produced, leading to the notion of dynamic graphs. An important query when analyzing graphs is to identify the most important vertices in a graph. Vertex importance is termed as centrality, and centrality scores can be used to provide rankings on the vertices of a graph. Specifically, I focus on Katz Centrality, a linear algebra based metric that measures the affinity between vertices in a graph as a weighted sum of the number of walks between them. Calculating Katz scores involves approximating the solution to a linear system using iterative solvers. Currently, we do not have a sense of how the numerical error from the iterative method in the approximation to the centrality vector affects the identification of the highly ranked vertices. In the first part of the talk, I bridge the two research areas of numerical analysis and network analysis by providing insight into how bounding the error between the approximate and exact solution in the numerical problem affects the correct relative ranking of vertices in the data mining problem. Typically, Katz scores are calculated through linear algebra. In the second section of the talk, I present an new alternative, agglomerative method of calculating personalized Katz scores. The algorithm presented is several orders of magnitude faster than the typical linear algebra approach and is able to return good quality scores of vertices. Finally, updating centrality scores of the vertices in a dynamic graph quickly becomes expensive to recompute from scratch every time the underlying graph is changed, as is the case in evolving networks. I conclude the talk by presenting a new algorithm for updating the Katz scores of vertices in a dynamic graph that is faster than static recomputation while maintaining good quality of the scores returned. |
| Title: On Cycles, Chorded Cycles, and Degree Conditions |
|---|
| Defense: Dissertation |
| Speaker: Ariel Keller of Emory University |
| Contact: Ariel Keller, ariel.keller@emory.edu |
| Date: 2018-03-01 at 3:00PM |
| Venue: MSC N301 |
| Download Flyer |
| Abstract: Sufficient conditions to imply the existence of certain substructures in a graph are of considerable interest in extremal graph theory, and conditions that guarantee a large set of cycles or chorded cycles are a recurring theme. This dissertation explores different degree sum conditions that are sufficient for finding a large set of vertex-disjoint cycles or a large set of vertex-disjoint chorded cycles in a graph. \vskip.1in For an integer $t\ge 1$, let $\sigma_t (G)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We first prove that if a graph $G$ has order at least $7k+1$ and degree sum condition $\sigma_4(G)\ge 8k-3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. Then, we consider an equivalent condition for chorded cycles, proving that if $G$ has order at least $11k+7$ and $\sigma_4(G)\ge 12k-3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint chorded cycles. We prove that the degree sum condition in each result is sharp. Finally, we conjecture generalized degree sum conditions on $\sigma_t(G)$ for $t\ge 2$ sufficient to imply that $G$ contains $k$ vertex-disjoint cycles for $k \ge 2$ and $k$ vertex-disjoint chorded cycles for $k \ge 2$. This is joint work with Ronald J. Gould and Kazuhide Hirohata. |
| Title: Counting points, counting fields, and heights on stacks |
|---|
| Colloquium: Algebra |
| Speaker: Jordan Ellenberg of University of Wisconsin-Madison |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2018-02-27 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: The basic objects of algebraic number theory are number fields, and the basic invariant of a number field is its discriminant, which in some sense measures its arithmetic complexity. A basic finiteness result is that there are only finitely many degree-$d$ number fields of discriminant at most $X$; more generally, for any fixed global field $K$, there are only finitely many degree-$d$ extensions $L/K$ whose discriminant has norm at most $X$. (The classical case is where $K = \mathbb{Q}$.) \\ When a set is finite, we greedily ask if we can compute its cardinality. Write $N_d(K,X)$ for the number of degree-$d$ extensions of $K$ with discriminant at most $d$. A folklore conjecture holds that $N_d(K,X)$ is on order $c_d X$. In the case $K = \mathbb{Q}$, this is easy for $d=2$, a theorem of Davenport and Heilbronn for $d=3$, a much harder theorem of Bhargava for $d=4$ and 5, and completely out of reach for $d > 5$. More generally, one can ask about extensions with a specified Galois group $G$; in this case, a conjecture of Malle holds that the asymptotic growth is on order $X^a (\log X)^b$ for specified constants $a,b$. \\ I'll talk about two recent results on this old problem: \\ 1) (joint with TriThang Tran and Craig Westerland) We prove that $N_d(\mathbb{F}_q(t),X)) < c_{\epsilon} X^{1+\epsilon}$ for all $d$, and similarly prove Malle’s conjecture ``up to epsilon" — this is much more than is known in the number field case, and relies on a new upper bound for the cohomology of Hurwitz spaces coming from quantum shuffle algebras: https://arxiv.org/abs/1701.04541 \\ 2) (joint with Matt Satriano and David Zureick-Brown) The form of Malle's conjecture is very reminiscent of the Batyrev-Manin conjecture, which says that the number of rational points of height at most $X$ on a Batyrev-Manin variety also grows like $X^a (\log X)^b$ for specified constants $a,b$. What’s more, an extension of $\mathbb{Q}$ with Galois group $G$ is a rational point on a Deligne--Mumford stack called $BG$, the classifying stack of $G$. A natural reaction is to say “the two conjectures is the same; to count number fields is just to count points on the stack BG with bounded height?” The problem: there is no definition of the height of a rational point on a stack. I'll explain what we think the right definition is, and explain how it suggests a heuristic which has both the Malle conjecture and the Batyrev--Manin conjecture as special cases. |
| Title: Reading Between the Lines of Datacenter Logs |
|---|
| Seminar: Computer Science |
| Speaker: Dr. Nosayba El-Sayed of MIT |
| Contact: TBA |
| Date: 2018-02-20 at 1:00PM |
| Venue: Atwood Chemistry Building Room 240 |
| Download Flyer |
| Abstract: Designing datacenters that are reliable, energy-efficient, and capable of delivering high performance and high utilization is a nontrivial problem facing scientists, businesses, and governments alike. In this talk, I will demonstrate how analyzing large datasets from different organizations helped us uncover interesting (and often surprising) patterns in the behavior of systems and applications in these large-scale platforms. I will show how real-world data helped us tackle critical questions such as how does temperature impact server reliability in places like Google, or how well do users configure the computing jobs they submit to shared clusters (spoiler alert: not very well!). Finally, I will demonstrate how simple machine learning techniques can be leveraged to accurately predict job failures in datacenters, while using data that is easily collected in current platforms. |
| Title: Joint Athens--Atlanta Number Theory Seminar |
|---|
| Seminar: Algebra |
| Speaker: David Harbater and Jacob Tsimerman of |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2018-02-20 at 4:00PM |
| Venue: TBA |
| Download Flyer |
| Abstract: Talks will be at the University of Georgia \\ \textbf{David Harbater} (University of Pennsylvania), 4:00 \\ Local-global principles for zero-cycles over semi-global fields \\ Classical local-global principles are given over global fields. This talk will discuss such principles over semi-global fields, which are function fields of curves defined over a complete discretely valued field. Paralleling a result that Y. Liang proved over number fields, we prove a local-global principle for zero-cycles on varieties over semi-global fields. This builds on earlier work about local-global principles for rational points. (Joint work with J.-L. Colliot-Thélène, J. Hartmann, D. Krashen, R. Parimala, J. Suresh.) \\ \textbf{Jacob Tsimerman} (U. Toronto), 5:15 \\ Cohen-Lenstra heuristics in the Presence of Roots of Unity \\ The class group is a natural abelian group one can associated to a number field, and it is natural to ask how it varies in families. Cohen and Lenstra famously proposed a model for families of quadratic fields based on random matrices of large rank, and this was later generalized by Cohen-Martinet to general number fields. However, their model was observed by Malle to have issues when the base field contains roots of unity. We explain that in this setting there are naturally defined additional invariants on the class group, and based on this we propose a refined model in the number field setting rooted in random matrix theory. Our conjecture is based on keeping track not only of the underlying group structure, but also certain natural pairings one can define in the presence of roots of unity. Specifically, if the base field contains roots of unity, we keep track of the class group G together with a naturally defined homomorphism $G^*[n] \to G$ from the n-torsion of the Pontryagin dual of G to G. Using methods of Ellenberg-Venkatesh-Westerland, we can prove some of our conjecture in the function field setting. |
| Title: Brauer classes supporting an involution |
|---|
| Seminar: Algebra |
| Speaker: Uriya First of University of Haifa |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2018-02-13 at 4:00PM |
| Venue: W304 |
| Download Flyer |
| Abstract: The construction of the Brauer group of a field can be generalized to (commutative) rings, and more generally to schemes, by replacing central simple algebras with Azumaya algebras. As in the case of fields, the Brauer group is an important cohomological invariant of the scheme, featuring, for instance, in the Manin obstruction for rational points. \\ Many of the properties of central simple algebras generalize to Azumaya algebras, but sometimes modifications are needed. For example, Albert characterized the central simple algebras admitting an involution of the first kind as those whose Brauer class is 2-torsion. While this fails for Azumaya algebras over a ring R, Saltman showed that the 2-torsion classes in the Brauer group of R are precisely those containing some representative admitting an involution of the first kind. Knus, Parimala and Srinivas later gave a quantitative version of this statement: If A is an Azumaya algebra of over R such that its Brauer class is 2-torsion, then there is an Azumaya algebra in the Brauer class of A that admits an involution and has degree 2*deg(A). \\ In this talk, we shall recall what are Azumaya algebras and how the Brauer group of a ring (or a scheme) is constructed. Then we will present a recent work with Asher Auel and Ben Williams where we use topological obstruction theory to show that the quantitative result of Knus, Parimala and Srinivas cannot be improved in general. Specifically, there are Azumaya algebras of degree 4 whose Brauer class is 2-torsion, but such that any algebra that is Brauer-equivalent to them and admits an involution has degree divisible by 8 = 2*4. |
| Title: Sparse Linear Algebra in the Exascale Era |
|---|
| Colloquium: Computational Mathematics |
| Speaker: Erin Carson of Courant Institute of Mathematical Sciences |
| Contact: James Nagy, jnagy@emory.edu |
| Date: 2018-02-13 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Sparse linear algebra problems, typically solved using iterative methods, are ubiquitous throughout scientific and data analysis applications and are often the most expensive computations in large-scale codes due to the high cost of data movement. Approaches to improving the performance of iterative methods typically involve modifying or restructuring the algorithm to reduce or hide this cost. Such modifications can, however, result in drastically different behavior in terms of convergence rate and accuracy. A clear, thorough understanding of how inexact computations, due to either finite precision error or intentional approximation, affect numerical behavior is thus imperative in balancing the tradeoffs between accuracy, convergence rate, and performance in practical settings. In this talk, we focus on two general classes of iterative methods for solving linear systems: Krylov subspace methods and iterative refinement. We present bounds on the attainable accuracy and convergence rate in finite precision s-step and pipelined Krylov subspace methods, two popular variants designed for high performance. For s-step methods, we demonstrate that our bounds on attainable accuracy can lead to adaptive approaches that both achieve efficient parallel performance and ensure that a user-specified accuracy is attained. We present two such adaptive approaches, including a residual replacement scheme and a variable s-step technique in which the parameter s is chosen dynamically throughout the iterations. Motivated by the recent trend of multiprecision capabilities in hardware, we present new forward and backward error bounds for a general iterative refinement scheme using three precisions. The analysis suggests that on architectures where half precision is implemented efficiently, it is possible to solve certain linear systems up to twice as fast and to greater accuracy. As we push toward exascale level computing and beyond, designing efficient, accurate algorithms for emerging architectures and applications is of utmost importance. We discuss extensions to machine learning and data analysis applications, the development of numerical autotuning tools, and the broader challenge of understanding what increasingly large problem sizes will mean for finite precision computation both in theory and practice. |
| Title: When the mesh is important: The role of anisotropic mesh adaptation in numerical modeling, from crack propagation to topology optimization |
|---|
| Colloquium: Computational Mathematics |
| Speaker: Simona Perotto of Politecnico di Milano, Italy |
| Contact: James Nagy, jnagy@emory.edu |
| Date: 2018-02-12 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Anisotropic mesh adaptation has been proved to be a powerful strategy for improving the quality and the efficiency of numerical modeling. Anisotropic phenomena occur in many applications, ranging from shocks in compressible flows, steep boundary or internal layers in viscous flows around bodies, fronts of different nature to be sharply tracked. These problems typically require advanced methods of scientific computing that rely on a tessellation or “mesh” of the region of interest. The intrinsic directionalities of these dynamics call for an accurate control of the shape, the size and the orientation of mesh elements in contrast to standard isotropic meshes where the only parameter to choose is the element size. Metric-based techniques usually drive anisotropic mesh adaptation, the metric being derived by either heuristic or theoretical approaches. In the former case, the metric is identified by a numerical approximation of the Hessian or of the gradient of the discrete solution, coupled with an a priori error estimator. More rigorous - theoretically based - approaches move from a posteriori error analyses, i.e., from an explicit control of the discretization error or – in more sophisticated cases – of a functional of the error. This control is enhanced by an appropriate inclusion of the main directional features of the problem at hand.\\ \\In this presentation, we focus on both heuristic and rigorous anisotropic error estimators. We present some theoretical aspects and applications to a variety of problems relevant for different fields, (i) propagation of cracks in brittle materials, (ii) topology optimization of structures for aerospace engineering (in collaboration with Thales Alenia Space) and (iii) medical image segmentation. |
| Title: Fast and stable algorithms for large-scale computation |
|---|
| Colloquium: Computational Mathematics |
| Speaker: Yuanzhe Xi of University of Minnesota |
| Contact: James Nagy, jnagy@emory.edu |
| Date: 2018-02-08 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Scientific computing and data analytics have become the third and fourth pillars of scientific discovery. Their success is tightly linked to a rapid increase in the size and complexity of problems and datasets of interest. In this talk, I will discuss our recent efforts in the development of novel numerical algorithms for tackling these challenges. In the first part, I will present a stochastic Lanczos algorithm for estimating the spectrum of Hermitian matrix pencils. The proposed algorithm only accesses the matrices through matrix-vector products and is suitable for large-scale computations. This algorithm is one of the key ingredients in the new breed of “spectrum slicing”-type eigensolvers for electronic structure calculations. In the second part, I will present our newly developed fast structured direct solvers for kernel systems and its applications in accelerating the learning process. By exploiting intrinsic low-rank property associated with the coefficient matrix, these structured solvers could overcome the cubic solution cost and quadratic storage cost of standard dense direct solvers and provide a new framework for performing various matrix operations in linear complexity. |