Seminars and Colloquia by Series

Conditionals on structural properties of strings and their stochastic counterparts in a declarative formalism

Series
Stochastics Seminar
Time
Thursday, November 13, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Anssi Yli-JyräHelsink University
Many context-free formalisms based on transitive properties of trees and strings have been converted to probabilitic models. We have Probabilistic Finite Automaton, Probabilistic Context Free Grammar and Probabilistic Tree Adjoining Grammars and many other probabilistic models of grammars. Typically such formalisms employ context-free productions that are transitively closed. Context-free grammars can be represented declaratively through context-sensitive grammars that analyse or check wellformedness of trees. When this direction is elaborated further, we obtain constraint-based representations for regular, context-free and mildly-context sensitive languages and their associated structures. Such representations can also be Probabilistic and this could be achieved by combining weighted rational operations and Dyck languages. More intuitively, the rational operations are packed to a new form of conditional rule: Generalized Restriction or GR in short (Yli-Jyrä and Koskenniemi 2004), or a predicate logic over strings. The conditional rule, GR, is flexible and provides total contexts, which is very useful e.g. when compiling rewriting rules for e.g. phonological alternations or speech or text normalization. However, the total contexts of different conditional rewriting rules can overlap. This implies that the conditions of different rules are not independent and the probabilities do not combine like in the case of context-free derivations. The non-transitivity causes problems for the general use of probabilistic Generalized Restriction e.g. when adding probabilities to phonological rewriting grammars that define regular relations.

Wolfgang Doeblin: A Mathematician Rediscovered

Series
Mathematical Finance/Financial Engineering Seminar
Time
Wednesday, November 12, 2008 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Christian HoudréSchool of Mathematics, Georgia Tech
In connection with the class Stochastic Processes in Finance II, we will have a supplementary lecture where a first, 50 minutes long, movie on Doeblin's life will be shown. This will be followed by a second movie, 30 minutes long, where Yor explains on the blackboard Doeblin's contribution to what Shreeve calls the Ito-Doeblin's lemma.

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

Series
ACO Student Seminar
Time
Wednesday, November 12, 2008 - 13:30 for 2 hours
Location
Skiles 269
Speaker
Gagan GoelACO Computer Science, Georgia Tech
We consider the following Maximum Budgeted Allocation(MBA) problem: Given a set of m indivisible items and n agents; each agent i is willing to pay b_ij amount of money on item j, and in addition he species the maximum amount (budget of B_i) he is willing to pay in total over all the items he receives. Goal is to allocate items to agents so as to maximize the total payment received from all the agents. The problem naturally arises as auctioneer revenue maximization in first price budget-constrained Auctions (For e.g. auctioning of TV/Radio ads by Google). Our main results are: 1) We give a 3/4-approximation algorithm for MBA improving upon the previous best of 0.632 [Anelman-Mansour, 04]. Our factor matches the integrality gap of the LP used by the previous results. 2) We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known. Our result also implies NP-hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276 [Feige-Vondrak, 07]. Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [Chekuri-Kumar, 04]. We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. Recently iterative rounding has achieved considerable success in designing approximation algorithms. However, these successes have been limited to minimization problems, and as per our knowledge, this work is the first iterative rounding based approximation algorithm for a natural maximization problem. We also give a (3/4 - \epsilon)-factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant \epsilon > 0. In this talk, I will present the iterative rounding based algorithm, show the hardness reductions, and put forward some directions which can help in solving the natural open question of closing the approximation gap. Joint work with Deeparnab Chakrabarty.

A Simple Quantitative Genetic Model of Parent-Offspring Interactions

Series
Mathematical Biology Seminar
Time
Wednesday, November 12, 2008 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Benjamin Ridenhour CDC/CCID/NCIRD, CTR
Parent-offspring interactions lead to natural conflicts. Offspring want as many resources as possible from parents in order to gain maximal fitness levels. On the other hand, parents desire to invest only enough to guarantee survival to reproduction. The resolution of the parent-offspring conflict has been a topic of much debate in evolutionary biology and typically invoke the concept of 'costs' to begging by offspring. Here I present the analysis of a simple quantitative genetic model of parent-offspring interactions that does not costs to resolve parent-offspring conflicts.

Uniqueness in the boundary inverse problem for elasticity

Series
PDE Seminar
Time
Tuesday, November 11, 2008 - 15:15 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Anna MazzucatoPenn State University, State College
We discuss the inverse problem of determining elastic parameters in the interior of an anisotropic elastic media from dynamic measurements made at the surface. This problem has applications in medical imaging and seismology. The boundary data is modeled by the Dirichlet-to-Neumann map, which gives the correspondence between surface displacements and surface tractions. We first show that, without a priori information on the anisotropy type, uniqueness can hold only up to change of coordinates fixing the boundary. In particular, we study orbits of elasticity tensors under diffeomorphisms. Then, we obtain partial uniqueness for special classes of transversely isotropic media. This is joint work with L. Rachele (RPI).

Trivialities, truths and lies about cubic graphs and Painleve I

Series
Analysis Seminar
Time
Monday, November 10, 2008 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Stavros GaroufalidisSchool of Mathematics, Georgia Tech
It is easy to ask for the number T(g,n) of (rooted) graphs with n edges on a surface of genus g. Bender et al gave an asymptotic expansion for fixed g and large n. The contant t_g remained missing for over 20 years, although it satisfied a complicated nonlinear recursion relation. The relation was vastly simplified last year. But a further simplification was made possible last week, thus arriving to Painleve I. I will review many trivialities and lies about this famous non-linear differential equation, from a post modern point of view.

Geometric flow approach to multiscale solvation modeling

Series
Applied and Computational Mathematics Seminar
Time
Monday, November 10, 2008 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Guowei WeiMichigan State University

Solvation process is of fundamental importance to other complex biological processes, such signal transduction, gene regulation, etc. Solvation models can be roughly divided into two classes: explicit solvent models that treat the solvent in molecular or atomic detail while implicit solvent models take a multiscale approach that generally replaces the explicit solvent with a dielectric continuum. Because of their fewer degrees of freedom, implicit solvent methods have become popular for many applications in molecular simulation with applications in the calculations of biomolecular titration states, folding energies, binding affinities, mutational effects, surface properties, and many other problems in chemical and biomedical research. In this talk, we introduce a geometric flow based multiscale solvation model that marries a microscopic discrete description of biomolecules with a macroscopic continuum treatment of the solvent. The free energy functional is minimized by coupled geometric and potential flows. The geometric flow is driven not only by intrinsic forces, such as mean curvatures, but also by extrinsic potential forces, such as those from electrostatic potentials. The potential flow is driven mainly by a Poisson-Boltzmann like operator. Efficient computational methods, namely the matched interface and boundary (MIB) method, is developed for to solve the Poisson- Boltzmann equation with discontinuous interface. A Dirichlet- to-Neumann mapping (DTN) approach is developed to regularize singular charges from biomolecules.

Green's Conjecture and Testing Linear-Invariant Properties

Series
Combinatorics Seminar
Time
Friday, November 7, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Asaf ShapiraSchool of Mathematics, Georgia Tech
Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant Boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S \subseteq [n], is \epsilon-far from being (M,b)-free if one needs to remove at least \epsilon n elements from S in order to make it (M,b)-free. The conjecture was that for any system of homogeneous linear equations Mx=0 and for any \epsilon > 0 there is a *constant* time algorithm that can distinguish with high probability between sets of integers that are (M,0)-free from sets that are \epsilon-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogeneous linear equations. As opposed to most results on testing Boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, R\"odl et al. and Austin and Tao.

Pages