Seminars and Colloquia Schedule

ARC Distinguished Lecture - Algorithmic Pricing

Series
Other Talks
Time
Monday, April 8, 2013 - 15:00 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Avrim Blum – Carnegie Mellon University
Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type. As one example, for the problem of pricing resources, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the i-th unit of each good at a value equal to the anticipated extraction cost of the 2i-th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions. I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.

Rota's conjecture, the missing axiom, and the tropical Laplacian

Series
Algebra Seminar
Time
Monday, April 8, 2013 - 16:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
June Huh – University of Michigan
Rota's conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. I will talk about Rota's conjecture and several related topics: the proof of the conjecture for representable matroids, a relation to the missing axiom, and a search for a new discrete Riemannian geometry based on the tropical Laplacian. This is an ongoing joint effort with Eric Katz.

Ferromagnetic crystals and the destruction of minimal foliations

Series
CDSNS Colloquium
Time
Monday, April 8, 2013 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bob W. Rink – Vrije Universiteit Amsterdam
A classical result of Aubry and Mather states that Hamiltonian twist maps have orbits of all rotation numbers. Analogously, one can show that certain ferromagnetic crystal models admit ground states of every possible mean lattice spacing. In this talk, I will show that these ground states generically form Cantor sets, if their mean lattice spacing is an irrational number that is easy to approximate by rational numbers. This is joint work with Blaz Mramor.

Geometric perspectives on phylogenetics

Series
Algebra Seminar
Time
Monday, April 8, 2013 - 17:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Seth Sullivant – North Carolina State University
I will discuss two problems in phylogenetics where a geometric perspective provides substantial insight. The first is the identifiability problem for phylogenetic mixture models, where the main problem is to determine which circumstances make it possible to recover the model parameters (e.g. the tree) from data. Here tools from algebraic geometry prove useful for deriving the current best results on the identifiability of these models. The second problem concerns the performance of distance-based phylogenetic algorithms, which take approximations to distances between species and attempt to reconstruct a tree. A classical result of Atteson gives guarantees on the reconstruction, if the data is not too far from a tree metric, all of whose edge lengths are bounded away from zero. But what happens when the true tree metric is very near a polytomy? Polyhedral geometry provides tools for addressing this question with some surprising answers.

ARC Theory Day

Series
Other Talks
Time
Tuesday, April 9, 2013 - 09:00 for 8 hours (full day)
Location
Klaus 1116
Speaker
ARC Theory Day – Algorithms and Randomness Center, Georgia Tech
Algorithms and Randomness Center (ARC) Theory Day is an annual event that features hour-long lectures focusing on recent innovative results in theoretical computer science, spanning a wide array of topics several of which are inspired by practical problems. See the complete list of titles and times of talks.

Cubic instability in Landau-de Gennes energy for nematic liquid crystals

Series
PDE Seminar
Time
Tuesday, April 9, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Xu, Xiang – Carnegie Mellon University
In the Landau-de Gennes theory to describe nematic liquid crystals, there exists a cubic term in the elastic energy, which is unusual but is used to recover the corresponding part of the classical Oseen-Frank energy. And the cost is that with its appearance the current elastic energy becomes unbounded from below. One way to deal with this unboundedness problem is to replace the bulk potential defined as in with a potential that is finite if and only if $Q$ is physical such that its eigenvalues are between -1/3 and 2/3. The main aim of our talk is to understand what can be preserved out of the physical relevance of the energy if one does not use a somewhat ad-hoc potential, but keeps the more common potential. In this case one cannot expect to obtain anything meaningful in a static theory, but one can attempt to see what a dynamical theory can predict.

RNA folding prediction: the continued need for interaction between biologists and mathematicians

Series
Research Horizons Seminar
Time
Wednesday, April 10, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Christine Heitsch – Georgia Tech, School of Math
A 1986 article with this title, written by M. Zuker and published by the AMS, outlined several major challenges in the area. Stating the folding problem is simple; given an RNA sequence, predict the set of (canonical, nested) base pairs found in the native structure. Yet, despite significant advances over the past 25 years, it remains largely unsolved. A fundamental problem identified by Zuker was, and still is, the "ill-conditioning" of discrete optimization solution approaches. We revisit some of the questions this raises, and present recent advances in considering multiple (sub)optimal structures, in incorporating auxiliary experimental data into the optimization, and in understanding alternative models of RNA folding.

"RNA folding prediction: the continued need for interaction between biologists and mathematicians"

Series
Research Horizons Seminar
Time
Wednesday, April 10, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Christine Heitsch – Georgia Institute of Technology, School of Mathematics –
A 1986 article with this title, written by M. Zuker and published by the AMS, outlined several major challenges in the area. Stating the folding problem is simple; given an RNA sequence, predict the set of (canonical, nested) base pairs found in the native structure. Yet, despite significant advances over the past 25 years, it remains largely unsolved. A fundamental problem identified by Zuker was, and still is, the "ill-conditioning" of discrete optimization solution approaches. We revisit some of the questions this raises, and present recent advances in considering multiple (sub)optimal structures, in incorporating auxiliary experimental data into the optimization, and in understanding alternative models of RNA folding.

Tightness and open book decompositions

Series
Geometry Topology Seminar
Time
Wednesday, April 10, 2013 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andy Wand – Harvard

Note different time and day.

A well known result of Giroux tells us that isotopy classes of contact structures on a closed three manifold are in one to one correspondence with stabilization classes of open book decompositions of the manifold. We will introduce a stabilization-invariant property of open books which corresponds to tightness of the corresponding contact structure. We will mention applications to the classification of contact 3-folds, and also to the question of whether tightness is preserved under Legendrian surgery.

Fast-slow partially hyperbolic systems beyond averaging.

Series
Math Physics Seminar
Time
Wednesday, April 10, 2013 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jacopo de Simoi – Universita' di Roma Tor Vergata
Lots of attention and research activity has been devoted to partially hyperbolic dynamical systems and their perturbations in the past few decades; however, the main emphasis has been on features such as stable ergodicity and accessibility rather than stronger statistical properties such as existence of SRB measures and exponential decay of correlations. In fact, these properties have been previously proved under some specific conditions (e.g. Anosov flows, skew products) which, in particular, do not persist under perturbations. In this talk, we will construct an open (and thus stable for perturbations) class of partially hyperbolic smooth local diffeomorphisms of the two-torus which admit a unique SRB measure satisfying exponential decay of correlations for Hölder observables. This is joint work with C. Liverani

Linkages and Their Behaviour

Series
School of Mathematics Colloquium
Time
Thursday, April 11, 2013 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Mark Pollicott – University of Warwick
The study of mechanical linkages is a very classical one, dating back to the Industrial Revolution. In this talk we will discuss the geometry of the configuration spaces in some simple idealized examples and, in particular, their curvature and geometry. This leads to an interesting quantitative description of their dynamical behaviour.

Slope heuristics and optimal excess risks bounds in heteroscedastic least-squares regression

Series
Stochastics Seminar
Time
Thursday, April 11, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skyles 006
Speaker
Adrien Saumard – University of Washington

References<br />
[1] S. Arlot and P. Massart. Data-driven calibration of penalties for least-squares regression. J. Mach. Learn.<br />
Res., 10:245.279 (electronic), 2009.<br />
[2] L. Birgé and P. Massart. Minimal penalties for Gaussian model selection. Probab. Theory Related Fields,<br />
138(1-2):33.73, 2007.<br />
[3] Vladimir Koltchinskii. Oracle inequalities in empirical risk minimization and sparse recovery problems,<br />
volume 2033 of Lecture Notes in Mathematics. Springer, Heidelberg, 2011. Lectures from the 38th Prob-<br />
ability Summer School held in Saint-Flour, 2008, École d.Été de Probabilités de Saint-Flour. [Saint-Flour<br />
Probability Summer School].<br />
[4] Pascal Massart. Concentration inequalities and model selection, volume 1896 of Lecture Notes in Math-<br />
ematics. Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in<br />
Saint-Flour, July 6.23, 2003, With a foreword by Jean Picard.

The systematical study of model selection procedures, especially since the early nineties, has led to the design of penalties that often allow to achieve minimax rates of convergence and adaptivity for the selected model, in the general setting of risk minimization (Koltchinskii [3], Massart [4]). However, the proposed penalties often su.er form their dependencies on unknown or unrealistic constants. As a matter of fact, under-penalization has generally disastrous e.ects in terms of e¢ ciency. Indeed, the model selection procedure then looses any bias-variance trade-o. and so, tends to select one of the biggest models in the collection. Birgé and Massart ([2]) proposed quite recently a method that empirically adjusts the level of penalization in a linear Gaussian setting. This method of calibration is called "slope heuristics" by the authors, and is proved to be optimal in their setting. It is based on the existence of a minimal penalty, which is shown to be half the optimal one. Arlot and Massart ([1]) have then extended the slope heuristics to the more general framework of empirical risk minimization. They succeeded in proving the optimality of the method in heteroscedastic least-squares regression, a case where the ideal penalty is no longer linear in the dimension of the models, not even a function of it. However, they restricted their analysis to histograms for technical reasons. They conjectured a wide range of applicability for the method. We will present some results that prove the validity of the slope heuristics in heteroscedastic least-squares regression for more general linear models than histograms. The models considered here are equipped with a localized orthonormal basis, among other things. We show that some piecewise polynomials and Haar expansions satisfy the prescribed conditions. We will insist on the analysis when the model is .xed. In particular, we will focus on deviations bounds for the true and empirical excess risks of the estimator. Empirical process theory and concentration inequalities are central tools here, and the results at a .xed model may be of independent interest.

Every locally characterized affine-invariant property is testable

Series
Combinatorics Seminar
Time
Friday, April 12, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Arnab Bhattacharyya – MIT
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties. [Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.]

Universal Conductivity Properties In Many Body Physics

Series
Math Physics Seminar
Time
Friday, April 12, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Vieri Mastropietro – Università degli Studi di Milano
Several low dimensional interacting fermionic systems, including g raphene and spin chains, exhibit remarkable universality properties in the c onductivity, which can be rigorously established under certain conditions by combining Renormal ization Group methods with Ward Identities.