- You are here:
- GT Home
- Home
- News & Events

Series: Geometry Topology Seminar

Series: Combinatorics Seminar

Series: Joint ACO and ARC Seminar

Is matching in NC, i.e., is there a deterministic fast parallel
algorithm for it? This has been an outstanding open question in TCS for
over three decades, ever since the discovery of Random NC matching
algorithms. Within this question, the case of planar graphs has remained
an enigma: On the one hand, counting the number of perfect matchings is
far harder than finding one (the former is #P-complete and the latter
is in P), and on the other, for planar graphs, counting has long been
known to be in NC whereas finding one has resisted a solution!The
case of bipartite planar graphs was solved by Miller and Naor in 1989
via a flow-based algorithm. In 2000, Mahajan and Varadarajan gave an
elegant way of using counting matchings to finding one, hence giving a
different NC algorithm.However, non-bipartite
planar graphs still didn't yield: the stumbling block being odd tight
cuts. Interestingly enough, these are also a key to the solution: a
balanced odd tight cut leads to a straight-forward divide and conquer NC
algorithm. The remaining task is to find such a cut in NC. This
requires several algorithmic ideas, such as finding a point in the
interior of the minimum weight face of the perfect matching polytope and
uncrossing odd tight cuts.Joint work with Nima Anari.

Series: Analysis Seminar

Wednesday, November 15, 2017 - 13:55 ,
Location: Skiles 006 ,
Surena Hozoori ,
Georgia Tech ,
Organizer: Jennifer Hom

Series: Algebra Seminar

Given a Galois cover of curves X to Y with Galois group G which is totally ramified at a point x and unramified elsewhere,
restriction to the punctured formal neighborhood of x induces a Galois extension of Laurent series rings k((u))/k((t)). If
we fix a base curve Y , we can ask when a Galois extension of Laurent series rings comes from a global cover of Y in this
way. Harbater proved that over a separably closed field, this local-to-global principle holds for any base curve if G is a
p-group, and gave a condition for the uniqueness of such an extension. Using a generalization of Artin-Schreier theory to
non-abelian p-groups, we characterize the curves Y for which this lifting property holds and when it is unique, but over
a more general ground field.

Monday, November 13, 2017 - 13:55 ,
Location: Skiles 005 ,
Tuo Zhao ,
Georgia Tech ,
Organizer: Wenjing Liao

Series: Geometry Topology Seminar

Series: GT-MAP Seminars

TBA

Series: Stochastics Seminar

We study an online algorithm for making a well—equidistributed random set of points in an interval, in the spirit of "power of choice" methods. Suppose finitely many distinct points are placed on an interval in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the interval. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We then study this point configuration in the sense of its largest interval, and discuss other "power of choice" type modifications.
Joint work with Pascal Maillard.