School of Mathematics

Matching: A New Proof for an Ancient Algorithm

Vijay Vazirani
Georgia Institute of Technology
December 10, 2012

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a ``black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm:
http://arxiv.org/abs/1210.4594

Nonlinear Long-Range Resonant Scattering and Kink Dynamics

Avy Soffer
Rutgers, The State University of New Jersey
December 7, 2012

We study the nonlinear Klein-Gordon equation, in one dimension, with a qudratic term and variable coefficient qubic term. This equation arises from the asymptotic stability theory of the kink solution.Our main result is the global existence and decay estimates for this equation. We discovered a striking new phenomena in this problem: a resonant interaction between the spacial frequencies of the nonlinear coefficient and the temporal oscillations of the solution.

Open-Closed Gromov-Witten Invariants of Toric Calabi-Yau 3-Orbifolds

Chiu-Chu Melissa Liu
Columbia University
December 7, 2012

We study open-closed orbifold Gromov-Witten invariants of toric Calabi-Yau 3-orbifolds with respect to Lagrangian branes of Aganagic-Vafa type. We prove an open mirror theorem which expresses generating functions of orbifold disk invariants in terms of Abel-Jacobi maps of the mirror curves. This is a joint work with Bohan Fang and Hsian-Hua Tseng.

Information Complexity and Exact Communication Bounds

Mark Braverman
Princeton University
December 3, 2012

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the AND of two bits distributed between Alice and Bob. We prove that the information complexity of AND is ~1.4923 bits. We use the optimal protocol and its properties to obtain tight bounds for the Disjointness problem, showing that the randomized communication complexity of Disjointness on n bits is ~0.4827n ± o(n).