Seminars and Colloquia by Series

Online Matching with Stochastic Rewards

Series
Graph Theory Seminar
Time
Tuesday, February 19, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Debmalya PanigrahiDuke University
The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio, and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)

Modeling the Electrical Activity in Cardiac Tissue

Series
Job Candidate Talk
Time
Tuesday, February 19, 2013 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 06
Speaker
Joyce T. Lin Univ of Utah
Electrical stimulation of cardiac cells causes an action potential wave to propagate through myocardial tissue, resulting in muscular contraction and pumping blood through the body. Approximately two thirds of unexpected, sudden cardiac deaths, presumably due to ventricular arrhythmias, occur without recognition of cardiac disease. While conduction failure has been linked to arrhythmia, the major players in conduction have yet to be well established. Additionally, recent experimental studies have shown that ephaptic coupling, or field effects, occurring in microdomains may be another method of communication between cardiac cells, bringing into question the classic understanding that action potential propagation occurs primarily through gap junctions. In this talk, I will introduce the mechanisms behind cardiac conduction, give an overview of previously studied models, and present and discuss results from a new model for the electrical activity in cardiac cells with simplifications that afford more efficient numerical simulation, yet capture complex cellular geometry and spatial inhomogeneities that are critical to ephaptic coupling.

Markov bases: discussion

Series
Other Talks
Time
Monday, February 18, 2013 - 17:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Pedro Rangel, Luo Ye, Robert KroneGeorgia Tech
We will discuss the details of the Markov bases chapter not covered in the previous talks.(Algebraic statistics reading seminar)

Log concavity of characteristic polynomials and tropical intersection theory

Series
Algebra Seminar
Time
Monday, February 18, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Eric KatzWaterloo
In a recent work with June Huh, we proved the log-concavity of the characteristic polynomial of a realizable matroid by relating its coefficients to intersection numbers on an algebraic variety and applying an algebraic geometric inequality. This extended earlier work of Huh which resolved a long-standing conjecture in graph theory. In this talk, we rephrase the problem in terms of more familiar algebraic geometry, outline the proof, and discuss an approach to extending this proof to all matroids. Our approach suggests a general theory of positivity in tropical geometry.

Higher order Markov random fields for independent sets

Series
Combinatorics Seminar
Time
Friday, February 15, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
David GoldbergISyE, Georgia Tech
We consider higher order Markov random fields to study independent sets in regular graphs of large girth (i.e. Bethe lattice, Cayley tree). We give sufficient conditions for a second-order homogenous isotropic Markov random field to exhibit long-range boundary independence (i.e. decay of correlations, unique infinite-volume Gibbs measure), and give both necessary and sufficient conditions when the relevant clique potentials of the corresponding Gibbs measure satisfy a log-convexity assumption. We gain further insight into this characterization by interpreting our model as a multi-dimensional perturbation of the hardcore model, and (under a convexity assumption) give a simple polyhedral characterization for those perturbations (around the well-studied critical activity of the hardcore model) which maintain long-range boundary independence. After identifying several features of this polyhedron, we also characterize (again as a polyhedral set) how one can change the occupancy probabilities through such a perturbation. We then use linear programming to analyze the properties of this set of attainable probabilities, showing that although one cannot acheive denser independent sets, it is possible to optimize the number of excluded nodes which are adjacent to no included nodes.

Courtesy Listing: Large-Scale Numerical Linear Algebra Techniques for Big Data Analysis

Series
Other Talks
Time
Friday, February 15, 2013 - 14:00 for 1 hour (actually 50 minutes)
Location
Klaus 2443
Speaker
Jie ChenArgonne National Laboratory

Please Note: Hosted by the School of Computational Science and Engineering

As the term "big data'' appears more and more frequently in our daily life and research activities, it changes our knowledge of how large the scale of the data can be and challenges the application of numerical analysis for performing statistical calculations. In this talk, I will focus on two basic statistics problems sampling a multivariate normal distribution and maximum likelihood estimation and illustrate the scalability issue that dense numerical linear algebra techniques are facing. The large-scale challenge motivates us to develop scalable methods for dense matrices, commonly seen in statistical analysis. I will present several recent developments on the computations of matrix functions and on the solution of a linear system of equations, where the matrices therein are large-scale, fully dense, but structured. The driving ideas of these developments are the exploration of the structures and the use of fast matrix-vector multiplications to reduce the general quadratic cost in storage and cubic cost in computation. "Big data'' offers a fresh opportunity for numerical analysts to develop algorithms with a central goal of scalability in mind. It also brings in a new stream of requests to high performance computing for highly parallel codes accompanied with the development of numerical algorithms. Scalable and parallelizable methods are key for convincing statisticians and practitioners to apply the powerful statistical theories on large-scale data that they currently feel uncomfortable to handle.

Conormals and contact homology V

Series
Geometry Topology Working Seminar
Time
Friday, February 15, 2013 - 11:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
John EtnyreGa Tech
In this series of talks I will begin by discussing the idea of studying smooth manifolds and their submanifolds using the symplectic (and contact) geometry of their cotangent bundles. I will then discuss Legendrian contact homology, a powerful invariant of Legendrian submanifolds of contact manifolds. After discussing the theory of contact homology, examples and useful computational techniques, I will combine this with the conormal discussion to define Knot Contact Homology and discuss its many wonders properties and conjectures concerning its connection to other invariants of knots in S^3.

Explicit Bounds for the Weak Structure Theorem

Series
Graph Theory Seminar
Time
Thursday, February 14, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Paul WollanUniversity of Rome and Georgia Tech
The Weak Structure Theorem of Robertson and Seymour is the cornerstone of many of the algorithmic applications of graph minors techniques. The theorem states that any graph which has both large tree-width and excludes a fixed size clique minor contains a large, nearly planar subgraph. In this talk, we will discuss a new proof of this result which is significantly simpler than the original proof of Robertson and Seymour. As a testament to the simplicity of the proof, one can extract explicit constants to the bounds given in the theorem. We will assume no previous knowledge about graph minors or tree-width. This is joint work with Ken Kawarabayashi and Robin Thomas

Hyperbolicity of the Arc and Curve Complex

Series
Geometry Topology Student Seminar
Time
Wednesday, February 13, 2013 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jamie ConwayGeorgia Tech
Given any surface, we can construct its curve complex by considering isotopy classes of curves on the surface. If the surface has boundary, we can construct its arc complex similarly, with isotopy clasess of arcs, with endpoints on the boundary. In 1999, Masur and Minsky proved that these complexes are hyperbolic, but the proof is long and involved. This talk will discuss a short proof of the hyperbolicity of the curve and arc complex recently given by Hensel, Przytycki, and Webb.

The Two Weight Inequality for the Hilbert Transform

Series
Research Horizons Seminar
Time
Wednesday, February 13, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael LaceyGeorgia Tech, School of Math
I'll introduce the Hilbert transform in a natural way justifying it as a canonical operation. In fact, it is such a basic operation, that it arises naturally in a range of settings, with the important complication that the measure spaces need not be Lebesge, but rather a pair of potentially exotic measures. Does the Hilbert transform map L^2 of one measure into L^2 of the other? The full characterization has only just been found. I'll illustrate the difficulties with a charming example using uniform measure on the standard 1/3 Cantor set.

Pages