UBC Department of Computer Science

Wed 25 Nov 2015, 3:00pm
Probability Seminar
ESB 2012

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles

ESB 2012
Wed 25 Nov 2015, 3:00pm4:00pm
Abstract
The Lovasz Local Lemma (LLL) is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space.
In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original LLL applies, there exist resampling oracles; and for essentially all known applications of the LLL we have designed efficient resampling oracles.
Our analysis is based on an alternative view of the LLL using multivariate polynomials, due to Shearer (and Scott and Sokal). Probabilists have also studied this topic under the name of "1dependent hardcore processes".
Joint work with Jan Vondrak (IBM Research).
hide


Thu 26 Nov 2015, 10:30am
Math Education Research Reading
Math126

"Mathematical Reasoning in Task Solving" by J. Lithner

Math126
Thu 26 Nov 2015, 10:30am11:30am
Abstract
hide

Washington State University

Thu 26 Nov 2015, 3:30pm
Number Theory Seminar
room IRMACS 10901 (SFU)

The distribution of integral points on homogeneous varieties

room IRMACS 10901 (SFU)
Thu 26 Nov 2015, 3:30pm4:30pm
Abstract
In this talk we will give a broad overview of the Linnik problems concerning the equidistribution of integral points on homogeneous varieties. One particular example concerns the Heegner points, which are roots in the complex upperhalf plane of certain quadratic forms. We will discuss certain "sparse" equidistribution problems concerning these points and give an application of an analog of Linnik's famous theorem on the first prime in an arithmetic progression. This is joint work with Riad Masri and Matt Young.
hide

UBC

Fri 27 Nov 2015, 12:00pm
Graduate Student Seminar
Math 103

The BanachTarski paradox (an introduction to the theory of amenability)

Math 103
Fri 27 Nov 2015, 12:00pm1:00pm
Abstract
This week, I will talk about the famous BanachTarski paradox to give an brief introduction to the theory of amenability. The goal will be to give an intuition of "what does it means to be amenable, aside from having a mean ?"
This theory is not only great because it provides a field dedicated to making bad puns with "mean", "amen" or even "ramen", it also has a lot of interesting characterizations.
We will give a little overview of BanachTarski paradox to motivate the topic (and quickly reattribute most of the result to Hausdorff), give a few alternative definitions and end up talking about graph theory.
Prerequisites : Be able to put up with my very average drawing skills, knowing how to pronounce Danish names always helps. Also, the axiom of choice is not optional, please don't be antichoice axiom.
hide

UBC Math

Fri 27 Nov 2015, 3:00pm
Department Colloquium
MATX 1100

Pathwaycentric modeling of microbial ecosystems (Graduate Research Award Colloquium)

MATX 1100
Fri 27 Nov 2015, 3:00pm4:00pm
Abstract
New molecular techniques such as DNA sequencing provide conceptual insights into microbial community metabolism and biogeochemical cycling in natural and engineered ecosystems. However, attempts to mechanistically integrate molecular data with biogeochemistry are faced with the inhibitory complexity of individual cells and a large number of unknown physiological parameters. Recent work suggests that biochemical pathways are, at ecosystem scales, strongly shaped by thermodynamic and stoichiometric constraints. Pathwaycentric mathematical theories rooted in fluxes of matter and energy could thus provide holistic insight into microbial ecosystems and global biogeochemical fluxes.
Oxygen minimum zones (OMZ) are oxygendepleted regions in the ocean that are dominated by microbial metabolism, thus constituting ideal systems for developing theories of microbial ecology. I will present our current efforts to model the biogeochemistry of an intensely studied OMZ off the coast of Vancouver Island using reactionadvectiondiffusion models. In contrast to conventional approaches, we focus on individual enzymes catalyzing metabolic pathways and assume that energy fluxes translate directly to gene expression and biosynthesis. We use DNA, mRNA and protein sequence data, as well as geochemical depth profiles and process rate measurements to calibrate and validate our models.
hide

Columbia

Mon 30 Nov 2015, 3:00pm
Algebraic Geometry Seminar
MATH 126

Relative orbifold DonaldsonThomas theory and local gerby curves

MATH 126
Mon 30 Nov 2015, 3:00pm4:00pm
Abstract
In this talk I will introduce the generalization of relative DonaldsonThomas theory to 3dimensional smooth DeligneMumford stacks. We adopt Jun Li’s construction of expanded pairs and degenerations and prove an orbifold DT degeneration formula. I’ll also talk about the application in the case of local gerby curves, and its relationship to the work of OkounkovPandharipande and MaulikOblomkov.
hide

University of Connecticutt/University of TexasSan Antonio

Tue 1 Dec 2015, 3:30pm
Diff. Geom, Math. Phys., PDE Seminar
ESB2012

Saddle Solutions of AllenCahn Equation on the Plane.

ESB2012
Tue 1 Dec 2015, 3:30pm4:30pm
Abstract
AllenCahn equation arises in the mathematical study of phase transition. Despite it's seemingly simple appearance, It has displayed very rich structure of solutions and involved
with deep mathematics. In this talk, I will discuss the existence, symmetry and classification of saddle solutions of AllenCahn equation on the plane. In particular, I will describe the variational characterization of these solutions as a mountain pass solutions.
hide

Note for Attendees
Pizza and pop will be provided.