Seminars and Colloquia by Series

Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs

Series
High-Dimensional Phenomena in Statistics and Machine Learning Seminar
Time
Tuesday, November 15, 2011 - 16:00 for 1.5 hours (actually 80 minutes)
Location
skyles 006
Speaker
Yingyu LiangSchool of Compter Science, Georgia tech
We will talk about how to approximate an arbitrary graph by a sparse graph with respect to cuts and flows, using random sampling techniques. More specifically, we will describe a near-linear-time randomized combinatorial construction that transforms any graph on n vertices into an O(n log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph's. The new graph can be used to accelerate cut and flow algorithms, leading to approximate solution on the original graph. The construction algorithms of the sparse graph are based on a general theorem analyzing the concentration of cut values near their expectation in random graphs.

The control polyhedron of a rational Bezier surface

Series
Algebra Seminar
Time
Monday, November 14, 2011 - 16:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Luis GarciaSam Houston State University
Geometric modeling builds computer models for industrial design and manufacture from basic units, called patches, such as, Bézier curves and surfaces. The control polygon of a Bézier curve is well-defined and has geometric significance—there is a sequence of weights under which the limiting position of the curve is the control polygon. For a Bezier surface patch, there are many possible polyhedral control structures, and none are canonical. In this talk, I will present a not necessarily polyhedral control structure for surface patches, regular control surfaces, which are certain C^0 spline surfaces. While not unique, regular control surfaces are exactly the possible limiting positions of a Bezier patch when the weights are allowed to vary. While our primary interest is to explain the meaning of control nets for the classical rational Bezier patches, we work in the generality of Krasauskas’ toric Bezier patches. Toric Bezier patches are multi-sided parametric patches based on the geometry of toric varieties and depend on a polytope and some weights. Our results rely upon a construction in computational algebraic geometry called a toric degeneration.

Applications of the knot Floer complex to concordance

Series
Geometry Topology Seminar
Time
Monday, November 14, 2011 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jen HomColumbia University
We will use a new concordance invariant, epsilon, associated to the knot Floer complex, to define a smooth concordance homomorphism. Applications include a new infinite family of smoothly independent topologically slice knots, bounds on the concordance genus, and information about tau of satellites. We will also discuss various algebraic properties of this construction.

Domain decomposition methods for large problems of elasticity

Series
Applied and Computational Mathematics Seminar
Time
Monday, November 14, 2011 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Olof Widlund Courant Institute,New York University, Mathematics and Computer Science
The domain decomposition methods considered are preconditioned conjugate gradient methods designed for the very large algebraic systems of equations which often arise in finite element practice. They are designed for massively parallel computer systems and the preconditioners are built from solvers on the substructures into whichthe domain of the given problem is partitioned. In addition, to obtain scalability, there must be a coarse problem, with a small number of degrees of freedom for each substructure. The design of this coarse problem is crucial for obtaining rapidly convergent iterations and poses the most interesting challenge in the analysis.Our work will be illustrated by overlapping Schwarz methods for almost incompressible elasticity approximated by mixed finite element and mixed spectral element methods. These algorithms is now used extensively at the SANDIA, Albuquerque laboratories and were developed in close collaboration with Dr. Clark R. Dohrmann. These results illustrate two roles of the coarse component of the preconditioner.Currently, these algorithms are being actively developed for problems posed in H(curl) and H(div). This work requires the development of new coarse spaces. We will also comment on recent work on extending domain decomposition theory to subdomains with quite irregular boundaries.  This work is relevant because of the use of mesh partitioners in the decomposition of large finite element matrices. 

Examples of negatively curved manifolds (after Ontaneda)

Series
Geometry Topology Working Seminar
Time
Friday, November 11, 2011 - 14:05 for 2 hours
Location
Skiles 006
Speaker
Igor BelegradekGeorgia Tech
This is the second in the series of two talks aimed to discuss a recent work of Ontaneda which gives a poweful method of producing negatively curved manifolds. Ontaneda's work adds a lot of weight to the often quoted Gromov's prediction that in a sense most manifolds (of any dimension) are negatively curved. In the second talk I shall discuss some ideas of the proof.

ARC Theory Day

Series
Other Talks
Time
Friday, November 11, 2011 - 09:20 for 1 hour (actually 50 minutes)
Location
Klaus 1116 E&W
Speaker
ARC Theory DayAlgorithms and Randomness Center, Georgia Tech
Algorithms and Randomness Center (ARC) Theory Day is an annual event, to showcase lectures on recent exciting developments in theoretical computer science. This year's inaugural event features four young speakers who have made such valuable contributions to the field. In addition, this year we are fortunate to have Avi Wigderson from the Institute for Advanced Study (Princeton) speak on fundamental questions and progress in computational complexity to a general audience. See the complete list of titles and times of talks.

The complete mixability and its applications

Series
Stochastics Seminar
Time
Thursday, November 10, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
skyles 006
Speaker
Ruodu WangSchool of mathematics, Georgia institute of Technology
The marginal distribution of identically distributed random variables having a constant sum is called a completely mixable distribution. In this talk, the concept, history and present research of the complete mixability will be introduced. I will discuss its relevance to existing problems in the Frechet class, i.e. problems with known marginal distributions but unknown joint distribution and its applications in quantitative risk management.

The power and weakness of randomness (when you are short on time)

Series
School of Mathematics Colloquium
Time
Thursday, November 10, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Avi WigdersonSchool of Mathematics, Institute for Advanced Study

Please Note: This is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011

Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.

Pages